Watch 10 video solutions for Minimize Result by Adding Parentheses to Expression, a medium level problem involving String, Enumeration. This walkthrough by Coding Decoded has 1,651 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.
Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.
Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.
The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
Example 1:
Input: expression = "247+38" Output: "2(47+38)" Explanation: Theexpressionevaluates to 2 * (47 + 38) = 2 * 85 = 170. Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the'+'. It can be shown that 170 is the smallest possible value.
Example 2:
Input: expression = "12+34" Output: "1(2+3)4" Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.
Example 3:
Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.
Constraints:
3 <= expression.length <= 10expression consists of digits from '1' to '9' and '+'.expression starts and ends with digits.expression contains exactly one '+'.expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.Problem Overview: You receive a string expression of the form num1+num2. The task is to insert a single pair of parentheses somewhere around the + so the resulting arithmetic value is minimized. Parentheses can extend into the digits on either side, which effectively multiplies surrounding numbers.
Approach 1: Brute Force Strategy From Both Sides (O(n^2) time, O(n) space)
Split the expression around the +. Then enumerate every possible position where the left parenthesis could start in the left number and every position where the right parenthesis could end in the right number. For each pair of positions, construct the expression and evaluate it as leftMultiplier * (insideLeft + insideRight) * rightMultiplier. Missing multipliers default to 1. This works because parentheses effectively isolate a portion of each number around the plus operator. The approach tries all combinations using simple string slicing and enumeration, then tracks the minimum result.
Approach 2: Optimized Computation with Consideration of Edge Cases (O(n^2) time, O(1) space)
The optimized version avoids repeatedly rebuilding strings or performing unnecessary conversions. Instead, iterate over all valid split indices while computing numeric segments directly. For each pair (i, j), treat the expression as four parts: prefix, leftInside, rightInside, and suffix. Convert only the necessary substrings to integers and compute the value using prefix * (leftInside + rightInside) * suffix. Edge cases occur when the prefix or suffix is empty; treat them as multiplier 1. This keeps the evaluation constant-time per configuration while still exploring all valid placements.
Recommended for interviews: Start with the brute force enumeration to show you understand how parentheses affect arithmetic grouping. Then move to the optimized computation that evaluates each candidate using numeric segments instead of constructing full expressions. Interviewers expect the O(n^2) enumeration solution because the search space is small and easy to reason about.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Strategy From Both Sides | O(n^2) | O(n) | When exploring all parenthesis placements directly using string slicing |
| Optimized Computation with Edge Case Handling | O(n^2) | O(1) | Preferred for interviews when minimizing conversions and computing numeric segments efficiently |