Place Parentheses for the Least Expression Value
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The string `expression` contains two positive integers separated by one `+`. Insert one pair of parentheses, with the opening parenthesis to the left of `+` and the closing parenthesis to its right, enclosing at least one digit from each side. Digits left outside the parentheses multiply the enclosed sum; an absent outside factor acts as one. Return a resulting expression with the smallest possible value. Keep every original digit and its order, and return any minimizing placement when several tie.
```cpp
class Solution {
public:
string minimizeResult(string expression);
};
```
### Examples
**Example 1:**
```text
expression = "11+11"
Output: "1(1+1)1"
Explanation: This evaluates to 2; the other placements evaluate to 12,12,22.
```
**Example 2:**
```text
expression = "23+4"
Output: "2(3+4)"
Explanation: It evaluates to 14, less than (23+4)=27.
```
### Constraints
- `3 <= expression.length <= 10`.
- Characters are digits 1 through 9 and exactly one plus sign; endpoints are digits.
- Every legal placement value, and the original sum, fit signed 32 bits.
### Clarifying Questions
Both inner operands are nonempty. A missing outer factor is one, not zero. Multiple optimal placements may be returned freely.
```hint Inspect the structure
How many choices exist for the opening position and closing position around the plus?
```
### What a Strong Answer Covers
- Consider only legal parentheses that enclose the plus and nonempty parts of both numbers.
- Evaluate the expression with the specified implicit multiplication and preserve all original characters.
- Justify global minimality while permitting every tied optimum.
### Follow-up Questions
How would allowing zero digits affect parsing or equality among candidates?
Overview: Place Parentheses for the Least Expression Value. The string expression contains two positive digit sequences separated by one plus sign. Insert exactly one pair of parentheses enclosing the plus and at least one digit from each side. Digits outside the parentheses act as multiplicative factors; an absent outside factor is one. Return any placement attaining the smallest value, preserving all original digits and their order.
