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 thatexpression evaluates to thesmallest 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.

Examples

Example 1

1
2
3

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The minimum value of the expression is 2 * (47 + 38) = 2 * 85 = 170.

Example 2

1
2
3

Input: expression = "12+34"
Output: "(12+34)"
Explanation: The minimum value is 46.

Constraints

  • 3 <= expression.length <= 10
  • expression consists of digits and exactly one ‘+’.
  • All digits are positive integers.

Solution

Method 1 – Enumeration

Intuition

Try all possible places to put the left and right parentheses around the ‘+’, and evaluate the resulting expression. The minimum value is achieved by the best split.

Approach

  1. Find the index of ‘+’.
  2. For every possible left parenthesis position before ‘+’, and every possible right parenthesis position after ‘+’, form the expression.
  3. Evaluate the value by splitting into four parts: left, inside left, inside right, right.
  4. Compute the value as (left or 1) * (inside left + inside right) * (right or 1).
  5. Track the minimum value and corresponding expression.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    string minimizeResult(string expr) {
        int plus = expr.find('+'), n = expr.size();
        int minVal = INT_MAX;
        string ans;
        for (int l = 0; l < plus; ++l) {
            for (int r = plus + 2; r <= n; ++r) {
                int left = l == 0 ? 1 : stoi(expr.substr(0, l));
                int inLeft = stoi(expr.substr(l, plus - l));
                int inRight = stoi(expr.substr(plus + 1, r - plus - 1));
                int right = r == n ? 1 : stoi(expr.substr(r));
                int val = left * (inLeft + inRight) * right;
                if (val < minVal) {
                    minVal = val;
                    ans = expr.substr(0, l) + "(" + expr.substr(l, plus - l) + "+" + expr.substr(plus + 1, r - plus - 1) + ")" + expr.substr(r);
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func minimizeResult(expr string) string {
    plus := strings.Index(expr, "+")
    n := len(expr)
    minVal := math.MaxInt32
    ans := ""
    for l := 0; l < plus; l++ {
        for r := plus+2; r <= n; r++ {
            left := 1
            if l > 0 {
                left, _ = strconv.Atoi(expr[:l])
            }
            inLeft, _ := strconv.Atoi(expr[l:plus])
            inRight, _ := strconv.Atoi(expr[plus+1:r])
            right := 1
            if r < n {
                right, _ = strconv.Atoi(expr[r:])
            }
            val := left * (inLeft + inRight) * right
            if val < minVal {
                minVal = val
                ans = expr[:l] + "(" + expr[l:plus] + "+" + expr[plus+1:r] + ")" + expr[r:]
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public String minimizeResult(String expr) {
        int plus = expr.indexOf('+'), n = expr.length();
        int minVal = Integer.MAX_VALUE;
        String ans = "";
        for (int l = 0; l < plus; ++l) {
            for (int r = plus + 2; r <= n; ++r) {
                int left = l == 0 ? 1 : Integer.parseInt(expr.substring(0, l));
                int inLeft = Integer.parseInt(expr.substring(l, plus));
                int inRight = Integer.parseInt(expr.substring(plus + 1, r));
                int right = r == n ? 1 : Integer.parseInt(expr.substring(r));
                int val = left * (inLeft + inRight) * right;
                if (val < minVal) {
                    minVal = val;
                    ans = expr.substring(0, l) + "(" + expr.substring(l, plus) + "+" + expr.substring(plus + 1, r) + ")" + expr.substring(r);
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun minimizeResult(expr: String): String {
        val plus = expr.indexOf('+')
        val n = expr.length
        var minVal = Int.MAX_VALUE
        var ans = ""
        for (l in 0 until plus) {
            for (r in plus + 2..n) {
                val left = if (l == 0) 1 else expr.substring(0, l).toInt()
                val inLeft = expr.substring(l, plus).toInt()
                val inRight = expr.substring(plus + 1, r).toInt()
                val right = if (r == n) 1 else expr.substring(r).toInt()
                val valRes = left * (inLeft + inRight) * right
                if (valRes < minVal) {
                    minVal = valRes
                    ans = expr.substring(0, l) + "(" + expr.substring(l, plus) + "+" + expr.substring(plus + 1, r) + ")" + expr.substring(r)
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def minimize_result(expression: str) -> str:
    plus = expression.index('+')
    n = len(expression)
    min_val = float('inf')
    ans = ''
    for l in range(plus):
        for r in range(plus+2, n+1):
            left = int(expression[:l]) if l > 0 else 1
            in_left = int(expression[l:plus])
            in_right = int(expression[plus+1:r])
            right = int(expression[r:]) if r < n else 1
            val = left * (in_left + in_right) * right
            if val < min_val:
                min_val = val
                ans = expression[:l] + '(' + expression[l:plus] + '+' + expression[plus+1:r] + ')' + expression[r:]
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn minimize_result(expr: String) -> String {
        let plus = expr.find('+').unwrap();
        let n = expr.len();
        let bytes = expr.as_bytes();
        let mut min_val = i32::MAX;
        let mut ans = String::new();
        for l in 0..plus {
            for r in plus+2..=n {
                let left = if l == 0 { 1 } else { expr[..l].parse::<i32>().unwrap() };
                let in_left = expr[l..plus].parse::<i32>().unwrap();
                let in_right = expr[plus+1..r].parse::<i32>().unwrap();
                let right = if r == n { 1 } else { expr[r..].parse::<i32>().unwrap() };
                let val = left * (in_left + in_right) * right;
                if val < min_val {
                    min_val = val;
                    ans = format!("{}({}+{}){}", &expr[..l], &expr[l..plus], &expr[plus+1..r], &expr[r..]);
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    minimizeResult(expression: string): string {
        const plus = expression.indexOf('+');
        const n = expression.length;
        let minVal = Number.MAX_SAFE_INTEGER;
        let ans = '';
        for (let l = 0; l < plus; ++l) {
            for (let r = plus + 2; r <= n; ++r) {
                const left = l === 0 ? 1 : Number(expression.slice(0, l));
                const inLeft = Number(expression.slice(l, plus));
                const inRight = Number(expression.slice(plus + 1, r));
                const right = r === n ? 1 : Number(expression.slice(r));
                const val = left * (inLeft + inRight) * right;
                if (val < minVal) {
                    minVal = val;
                    ans = expression.slice(0, l) + '(' + expression.slice(l, plus) + '+' + expression.slice(plus + 1, r) + ')' + expression.slice(r);
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
    • Two nested loops over the length of the string.
  • 🧺 Space complexity: O(n)
    • For storing the answer string.