LeetCode 2232 - Minimize Result by Adding Parentheses to Expression

LeetCode Problem 2232

Difficulty: 🟡 Medium
Topics: String, Enumeration

Solution

Problem Understanding

The problem presents a string expression in the form "<num1>+<num2>", where both <num1> and <num2> are positive integers represented as strings. The task is to insert exactly one pair of parentheses such that the left parenthesis appears to the left of the plus sign and the right parenthesis appears to the right of the plus sign, resulting in a valid arithmetic expression that evaluates to the minimum possible integer value.

For example, if the input is "247+38", we can place the parentheses in several valid ways like "2(47+38)", "24(7+38)", and "(247+38)". Each option evaluates to a different numeric result, and we want the one that gives the smallest result. The final output must return the expression with the parentheses, not the evaluated numeric value.

The constraints are strict but manageable: the string length is small (3 <= expression.length <= 10) and there is exactly one '+'. Because of this, the problem allows a brute-force enumeration over all possible locations to insert the parentheses without worrying about performance issues.

Important edge cases include very small numbers, numbers of length 1, or placing parentheses such that they wrap the entire expression. The problem guarantees that the final result fits within a 32-bit signed integer.

Approaches

Brute Force Approach

The brute-force solution involves trying every valid way to insert the left and right parentheses. For an expression like "num1+num2", we can:

1. Iterate over every possible split point in num1 for the left parenthesis.
2. Iterate over every possible split point in num2 for the right parenthesis.
3. Evaluate the numeric result of the expression after applying the parentheses.
4. Track the minimum value and its corresponding parenthesized expression.

Because num1 and num2 are both at most 9 digits long (from constraints), this brute-force approach is feasible, as the total number of combinations is less than 100, which is trivial to compute.

Optimal Approach

The optimal approach is conceptually similar to brute force but focuses on reducing unnecessary operations by considering that multiplying by 1 does not change the sum. Therefore, we iterate over all possible splits but compute the multiplication efficiently using integer arithmetic, avoiding unnecessary string-to-int conversions for repeated segments. This approach guarantees the minimum value by checking all valid splits.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Try all split points for left and right parentheses. Feasible since n ≤ 10
Optimal	O(n^2)	O(1)	Same as brute-force but with careful arithmetic evaluation and string reconstruction

Algorithm Walkthrough

1. Split the input string into num1 and num2 based on the '+' character. This helps isolate the two numbers for processing.
2. Initialize min_value to infinity and result_expression to an empty string.
3. Iterate over all possible positions to place the left parenthesis in num1. Let i range from 0 to len(num1) - 1. The left parenthesis goes before num1[i].
4. Iterate over all possible positions to place the right parenthesis in num2. Let j range from 1 to len(num2). The right parenthesis goes after num2[j-1].
5. Split num1 into a prefix (num1[:i]) and suffix (num1[i:]), and num2 into prefix (num2[:j]) and suffix (num2[j:]).
6. Evaluate the total value of the expression: (left_multiplier * (middle_sum) * right_multiplier), where:

• left_multiplier is int(num1[:i]) or 1 if empty
• middle_sum is int(num1[i:]) + int(num2[:j])
• right_multiplier is int(num2[j:]) or 1 if empty

7. If this evaluated value is smaller than min_value, update min_value and store the corresponding parenthesized expression.
8. Return the stored expression once all combinations have been evaluated.

Why it works: The algorithm exhaustively checks every valid placement of parentheses. The structure of arithmetic guarantees that multiplying a sum by numbers outside the parentheses covers all possible evaluation scenarios, ensuring the minimum is found.

Python Solution

class Solution:
    def minimizeResult(self, expression: str) -> str:
        plus_index = expression.index('+')
        num1 = expression[:plus_index]
        num2 = expression[plus_index+1:]
        
        min_value = float('inf')
        result_expression = ""
        
        for i in range(len(num1)):
            left = num1[:i]
            left_multiplier = int(left) if left else 1
            num1_suffix = num1[i:]
            
            for j in range(1, len(num2)+1):
                num2_prefix = num2[:j]
                num2_suffix = num2[j:]
                middle_sum = int(num1_suffix) + int(num2_prefix)
                right_multiplier = int(num2_suffix) if num2_suffix else 1
                total = left_multiplier * middle_sum * right_multiplier
                
                if total < min_value:
                    min_value = total
                    result_expression = f"{left}({num1_suffix}+{num2_prefix}){num2_suffix}"
        
        return result_expression

The Python solution first separates the two numbers around the plus sign. It then iterates over all potential positions to insert parentheses, carefully handling empty strings by treating them as 1 for multiplication. After computing each possible total, it updates the minimum and builds the corresponding expression. The final result is returned once all possibilities are evaluated.

Go Solution

import (
    "strconv"
    "math"
)

func minimizeResult(expression string) string {
    plusIndex := 0
    for i, c := range expression {
        if c == '+' {
            plusIndex = i
            break
        }
    }
    num1 := expression[:plusIndex]
    num2 := expression[plusIndex+1:]
    
    minValue := math.MaxInt32
    resultExpr := ""
    
    for i := 0; i < len(num1); i++ {
        left := num1[:i]
        leftMultiplier := 1
        if left != "" {
            leftMultiplier, _ = strconv.Atoi(left)
        }
        num1Suffix := num1[i:]
        
        for j := 1; j <= len(num2); j++ {
            num2Prefix := num2[:j]
            num2Suffix := num2[j:]
            middleSum, _ := strconv.Atoi(num1Suffix)
            tmp, _ := strconv.Atoi(num2Prefix)
            middleSum += tmp
            
            rightMultiplier := 1
            if num2Suffix != "" {
                rightMultiplier, _ = strconv.Atoi(num2Suffix)
            }
            
            total := leftMultiplier * middleSum * rightMultiplier
            if total < minValue {
                minValue = total
                resultExpr = left + "(" + num1Suffix + "+" + num2Prefix + ")" + num2Suffix
            }
        }
    }
    
    return resultExpr
}

The Go solution follows the same logic as Python. Go requires explicit conversion between strings and integers using strconv.Atoi and careful handling of empty strings. The nested loops generate all possible placements, compute the corresponding arithmetic value, and track the minimum.

Worked Examples

Example 1: "247+38"

Left index i	Right index j	Expression	Computed Value
0	1	(247+3)8	250 * 8 = 2000
0	2	(247+38)	285
1	1	2(47+3)8	2_50_8 = 800
1	2	2(47+38)	2*85 = 170

Minimum value is 170, expression is 2(47+38).

Example 2: "12+34"

Left index i	Right index j	Expression	Computed Value
0	1	(12+3)4	15*4 = 60
0	2	(12+34)	46
1	1	1(2+3)4	1_5_4 = 20
1	2	1(2+34)	36

Minimum value is 20, expression is 1(2+3)4.

Example 3: "999+999"

Only one valid placement that minimizes: (999+999) = 1998.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Two nested loops over num1 and num2 possible split points, where n ≤ 10
Space	O(1)	Only a few integer and string variables used, no extra data structures

The complexity is small because expression has length at most 10, making the nested iteration feasible. Each arithmetic operation is constant time since the numbers involved fit in 32-bit integers.

Test Cases

# Provided examples
assert Solution