# Minimize Result by Adding Parentheses to Expression
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-result-by-adding-parentheses-to-expression)
Canonical: https://scaleengineer.com/dsa/problems/minimize-result-by-adding-parentheses-to-expression
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
**Companies:** [Snap](https://scaleengineer.com/companies/snap), [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## Problem
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:** 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"
**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 <= 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.

# Approaches
## Brute-Force with Repeated String Building
This approach systematically explores every possible valid placement for the parentheses. For each placement, it calculates the resulting expression's value and keeps track of the placement that yields the minimum value found so far.
**Time:** O(L * R * N), where `L` is the length of the first number, `R` is the length of the second number, and `N` is the total length of the expression. The nested loops run `L * R` times. Inside the loop, `substring` operations, `parseLong`, and string concatenation take `O(N)` time in total. Given `N <= 10`, this is very fast. · **Space:** O(N) to store the resulting string, where N is the length of the expression.
**Pros:** Guaranteed to find the optimal solution because it checks every possibility.; Simple and straightforward to implement.
**Cons:** Inefficient due to repeated string construction inside the loops. For each new minimum found, a new result string is created, which involves memory allocation and copying.
### Explanation
The core idea is to iterate through all possible split points for the two numbers around the `+` sign.
Let the expression be `num1+num2`. The left parenthesis `(` can be inserted at any position within `num1`, and the right parenthesis `)` can be inserted at any position within `num2`. This partitions the expression into four parts: `A(B+C)D`.
- `A`: The part of `num1` before the `(`. Can be empty.
- `B`: The part of `num1` after the `(`.
- `C`: The part of `num2` before the `)`.
- `D`: The part of `num2` after the `)`. Can be empty.

The value of the expression is `val(A) * (val(B) + val(C)) * val(D)`. If `A` or `D` is empty, its value is considered 1.

The algorithm proceeds as follows:
1.  Find the index of the `+` operator.
2.  Initialize `minVal` to a very large number and `result` to an empty string.
3.  Use a nested loop:
    - The outer loop iterates through all possible positions `i` to place the `(`. This position `i` splits `num1`.
    - The inner loop iterates through all possible positions `j` to place the `)`. This position `j` splits `num2`.
4.  Inside the loops, for each pair of `(i, j)`:
    a.  Extract the four substrings corresponding to `A`, `B`, `C`, and `D`.
    b.  Parse them into integers. Handle empty strings for `A` and `D` by using a value of 1.
    c.  Calculate the total value: `valA * (valB + valC) * valD`.
    d.  If this value is less than `minVal`, update `minVal` and reconstruct the entire expression string with parentheses at the current positions `i` and `j`. Store this new string in `result`.
5.  After checking all possibilities, `result` will hold the expression that evaluates to the smallest value.

```java
class Solution {
    public String minimizeResult(String expression) {
        int plusIndex = expression.indexOf('+');
        long minVal = Long.MAX_VALUE;
        String result = "";

        // i is the split point for the left number (num1)
        // It's the index where '(' is inserted.
        for (int i = 0; i < plusIndex; i++) {
            // j is the split point for the right number (num2)
            // It's the index of the last digit inside the parenthesis.
            for (int j = plusIndex + 1; j < expression.length(); j++) {
                // Part 1: Left multiplier
                String p1Str = expression.substring(0, i);
                long p1 = p1Str.isEmpty() ? 1 : Long.parseLong(p1Str);

                // Part 2: First number in sum
                String p2Str = expression.substring(i, plusIndex);
                long p2 = Long.parseLong(p2Str);

                // Part 3: Second number in sum
                String p3Str = expression.substring(plusIndex + 1, j + 1);
                long p3 = Long.parseLong(p3Str);

                // Part 4: Right multiplier
                String p4Str = expression.substring(j + 1);
                long p4 = p4Str.isEmpty() ? 1 : Long.parseLong(p4Str);

                long currentVal = p1 * (p2 + p3) * p4;

                if (currentVal < minVal) {
                    minVal = currentVal;
                    result = p1Str + "(" + p2Str + "+" + p3Str + ")" + p4Str;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Find the index of the `+` sign, let's call it `plusIndex`.
- Initialize `minVal` to infinity and `resultExpression` to an empty string.
- Iterate with a loop for the left parenthesis position `i` from `0` to `plusIndex - 1`.
- Inside this loop, iterate with another loop for the right parenthesis position `j` from `plusIndex + 1` to `expression.length() - 1`.
- In the inner loop:
    - Split the expression into four parts based on `i` and `j`.
    - Parse these parts into numbers, treating empty parts as multipliers of 1.
    - Calculate the value of the expression `part1 * (part2 + part3) * part4`.
    - If the calculated value is smaller than `minVal`:
        - Update `minVal` with the new smaller value.
        - Construct the parenthesized string and update `resultExpression`.
- Return `resultExpression`.

## Optimized Brute-Force by Deferring String Construction
This approach uses the same brute-force strategy of checking all parenthesis placements but optimizes the process by avoiding repeated string manipulations. Instead of building the result string every time a new minimum is found, it only stores the indices of the best placement and constructs the final string only once after all possibilities have been evaluated.
**Time:** O(L * R * N). The asymptotic complexity is the same as the previous approach. However, it is practically faster as the `O(N)` string construction work is moved outside the `L*R` iterations. The work inside the loop is dominated by parsing, which takes `O(N)` time. The final string construction also takes `O(N)`. The total time is `O(L*R*N + N)`, which simplifies to `O(L*R*N)`. · **Space:** O(N) for storing the final string using a `StringBuilder`. Extra space for indices is `O(1)`.
**Pros:** More efficient in practice by avoiding repeated, potentially expensive, string allocations and constructions within the loops.; Better separation of concerns: finding the minimum is done first, then formatting the output.
**Cons:** The asymptotic time complexity is not improved, as the bottleneck is the nested loop structure and parsing, not the string building for the given small constraints.
### Explanation
The fundamental logic is identical to the first approach: iterate through all possible split points `i` and `j` and calculate the resulting value. The key difference lies in how the result is managed.

The algorithm is as follows:
1.  Find the index of the `+` operator.
2.  Initialize `minVal` to a very large number.
3.  Initialize `best_i` and `best_j` to store the indices of the best parenthesis placement found so far.
4.  Use the same nested loop structure to iterate through all positions `i` and `j`.
5.  Inside the loops:
    a.  Extract and parse the four numerical parts `valA`, `valB`, `valC`, `valD` as before.
    b.  Calculate the total value.
    c.  If this value is less than `minVal`, update `minVal` and, importantly, update `best_i = i` and `best_j = j`. We do **not** build the string here.
6.  After the loops finish, we will have the minimum possible value `minVal` and the indices `best_i` and `best_j` that produce it.
7.  Construct the final result string *once* using the stored `best_i` and `best_j` indices. This is done by inserting `(` at `best_i` and `)` at `best_j + 1`.

```java
class Solution {
    public String minimizeResult(String expression) {
        int plusIndex = expression.indexOf('+');
        long minVal = Long.MAX_VALUE;
        int bestI = -1, bestJ = -1;

        // i is the split point for the left number (num1)
        // It's the index where '(' is inserted.
        for (int i = 0; i < plusIndex; i++) {
            // j is the split point for the right number (num2)
            // It's the index of the last digit inside the parenthesis.
            for (int j = plusIndex + 1; j < expression.length(); j++) {
                String p1Str = expression.substring(0, i);
                long p1 = p1Str.isEmpty() ? 1 : Long.parseLong(p1Str);

                String p2Str = expression.substring(i, plusIndex);
                long p2 = Long.parseLong(p2Str);

                String p3Str = expression.substring(plusIndex + 1, j + 1);
                long p3 = Long.parseLong(p3Str);

                String p4Str = expression.substring(j + 1);
                long p4 = p4Str.isEmpty() ? 1 : Long.parseLong(p4Str);

                long currentVal = p1 * (p2 + p3) * p4;

                if (currentVal < minVal) {
                    minVal = currentVal;
                    bestI = i;
                    bestJ = j;
                }
            }
        }

        // Construct the result string once at the end
        StringBuilder sb = new StringBuilder(expression);
        sb.insert(bestJ + 1, ')');
        sb.insert(bestI, '(');
        return sb.toString();
    }
}
```
### Algorithm
- Find the index of the `+` sign, `plusIndex`.
- Initialize `minVal` to infinity, and `bestI`, `bestJ` to -1.
- Iterate with a loop for the left parenthesis position `i` from `0` to `plusIndex - 1`.
- Inside, iterate with a loop for the right parenthesis end position `j` from `plusIndex + 1` to `expression.length() - 1`.
- In the inner loop:
    - Split and parse the expression into four numerical parts.
    - Calculate the value.
    - If the value is smaller than `minVal`:
        - Update `minVal`.
        - Store the current indices: `bestI = i`, `bestJ = j`.
- After the loops, use `bestI` and `bestJ` to construct the final parenthesized string.
- Return the constructed string.

# Solutions
### Java

```java
class Solution {
public
  String minimizeResult(String expression) {
    int idx = expression.indexOf('+');
    String l = expression.substring(0, idx);
    String r = expression.substring(idx + 1);
    int m = l.length(), n = r.length();
    int mi = Integer.MAX_VALUE;
    String ans = "";
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int c = Integer.parseInt(l.substring(i)) +
                Integer.parseInt(r.substring(0, j + 1));
        int a = i == 0 ? 1 : Integer.parseInt(l.substring(0, i));
        int b = j == n - 1 ? 1 : Integer.parseInt(r.substring(j + 1));
        int t = a * b * c;
        if (t < mi) {
          mi = t;
          ans = String.format("%s(%s+%s)%s", l.substring(0, i), l.substring(i),
                              r.substring(0, j + 1), r.substring(j + 1));
        }
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def minimizeResult(self, expression: str) -> str: l, r = expression . split("+") m, n = len(l), len(r) mi = inf ans = None for i in range(m): for j in range(n): c = int(l[i:]) + int(r[: j + 1]) a = 1 if i == 0 else int(l[: i]) b = 1 if j == n - 1 else int(r[j + 1:]) if (t: = a * b * c) < mi: mi = t ans = f " { l [ : i ] } ( { l [ i : ] } + { r [ : j + 1 ] } ) { r [ j + 1 : ] } " return ans

```