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.In #2232 Minimize Result by Adding Parentheses to Expression, the expression contains a single '+' and the goal is to insert one pair of parentheses so the resulting evaluated value is minimized. The key observation is that parentheses will wrap a portion of the left number and a portion of the right number around the plus sign.
A practical strategy is enumeration. Iterate over every possible position to place the opening parenthesis in the left part and every possible position to place the closing parenthesis in the right part. For each combination, interpret the expression as a * (b + c) * d, where b + c is the portion inside the parentheses and a and d are optional multipliers formed by digits outside the parentheses.
For each candidate placement, compute the resulting value and track the minimum. Since the expression length is small, checking all valid placements is efficient. The approach typically runs in O(n^2) time due to trying all pairs of boundaries, with O(1) extra space aside from string handling.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Enumeration of all parenthesis placements | O(n^2) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
The maximum length of expression is very low. We can try every possible spot to place the parentheses.
Every possibility of expression is of the form a * (b + c) * d where a, b, c, d represent integers. Note the edge cases where a and/or d do not exist, in which case use 1 instead of them.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The input size is relatively small and there is only one plus operator in the expression. This means the number of valid parenthesis placements is limited, allowing all possibilities to be checked efficiently without needing advanced optimization techniques.
Yes, similar problems appear in technical interviews because they test string parsing, enumeration, and careful handling of arithmetic expressions. Companies often use such problems to evaluate a candidate's ability to reason about edge cases and brute-force optimizations.
No complex data structure is required for this problem. Basic string manipulation and integer calculations are sufficient. The solution mainly relies on iterating through possible split positions in the string.
The optimal approach is to enumerate all possible positions for placing the opening and closing parentheses around the '+' sign. For each placement, evaluate the expression as a multiplication of the outer parts and the inner sum. Track the minimum value produced among all combinations.