Minimize Result by Adding Parentheses to Expression

For LeetCode 2232, the key is to try every place to open before the plus and every place to close after it. Each choice turns the expression into leftPrefix * (middleLeft + middleRight) * rightSuffix, where missing outer parts act like 1. Because the string is very short, full enumeration is the cleanest and safest solution.

Problem Statement

You are given a string expression containing exactly one plus sign, where the left and right sides are positive integers written with digits only. You must insert one left parenthesis somewhere before the plus sign and one right parenthesis somewhere after the plus sign, so the new expression stays valid and the parenthesized sum includes the plus.

Your goal is to return the parenthesized expression that produces the smallest possible value after evaluation. If characters remain outside the parentheses, they multiply the value inside, so the real task is not just splitting the string but finding the placement that minimizes this multiplication effect. If multiple placements give the same minimum value, any one of them is acceptable.

Examples

Example 1

Input: expression = "247+38"

Output: "2(47+38)"

The expression evaluates 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"

The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.

Example 3

Input: expression = "999+999"

Output: "(999+999)"

The expression evaluates to 999 + 999 = 1998.

Constraints

• 3 <= expression.length <= 10
• expression consists of digits from '1' to '9' and '+'.
• expression starts and ends with digits.
• expression contains exactly one '+'.
• 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.

Solution Approach

Split around the single plus sign

First find the index of the only plus sign. Every valid answer must place the left parenthesis somewhere in the left number and the right parenthesis somewhere in the right number, so the search space is fully determined by that split.

Enumerate every valid parenthesis boundary

Try each start index on the left side and each end index on the right side. For each pair, parse four parts: the prefix before the left parenthesis, the left part inside the parentheses, the right part inside the parentheses, and the suffix after the right parenthesis. Evaluate the candidate as prefixValue * (insideLeft + insideRight) * suffixValue, treating an empty prefix or suffix as 1.

Track the minimum and rebuild the best string

Keep the smallest evaluated value seen so far and store the corresponding formatted expression. Since expression length is at most 10, repeated substring parsing is cheap, and this brute-force enumeration avoids the main failure mode of trying to guess a greedy cut that looks locally good but loses globally.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Let L be the number of digits before the plus and R be the number of digits after it. There are L * R valid parenthesis placements to test, and each evaluation uses only small substring work, so the time complexity is O(L * R). Since the full expression length is at most 10, this is effectively constant time in practice. Extra space is O(1) aside from temporary substring handling and the output string.

What Interviewers Usually Probe

• They point out that the expression length is tiny, which is a strong signal to enumerate all parenthesis placements.
• They ask how multiplication appears after adding parentheses, which hints that outside digits become prefix and suffix multipliers.
• They care more about correctness than clever pruning, which usually means brute force is the intended pattern for this String plus Enumeration problem.

Common Pitfalls or Variants

Common pitfalls

• Forgetting that an empty prefix or empty suffix should contribute 1, not 0, which breaks cases like (999+999).
• Placing parentheses in invalid positions, such as ending before the plus or starting after it, which violates the problem constraints.
• Using a greedy idea like minimizing the inside sum alone, even though a slightly larger sum can still win if it avoids a large outer multiplier.

Follow-up variants

• Return the minimum numeric value instead of the final parenthesized string.
• Allow multiple plus signs, which turns simple enumeration into a more complex expression optimization problem.
• Ask for the maximum result instead of the minimum, which keeps the same enumeration structure but flips the comparison.

FAQ

What is the main idea for Minimize Result by Adding Parentheses to Expression?

Try every valid place to open before the plus and every valid place to close after it, evaluate each result, and keep the minimum. The short input length makes full enumeration the intended approach.

Why does this problem use String plus Enumeration instead of greedy logic?

A greedy cut can fail because the final value depends on both the sum inside the parentheses and the multipliers created by digits left outside. Enumeration works because the search space is tiny and captures that trade-off exactly.

How do I evaluate one parenthesis placement correctly?

Split the expression into prefix, inside-left, inside-right, and suffix. Compute prefix * (inside-left + inside-right) * suffix, and treat a missing prefix or suffix as 1.

Why is "2(47+38)" the best answer for "247+38"?

That placement gives 2 * (47 + 38) = 170. Other valid placements either make the inside sum smaller but leave a bigger multiplier outside, or keep too many digits outside and produce a larger final value.

What are the time and space costs for LeetCode 2232?

If there are L digits before the plus and R digits after it, there are L * R candidates to test, so time is O(L * R). Extra space is O(1) besides temporary parsing and the returned string.