Minimize Result by Adding Parentheses to Expression

Medium Arrays & Hashing Candidate Generation Original on LeetCode

Minimize Result by Adding Parentheses to Expression is a medium arrays & hashing problem solved with the candidate generation pattern. The best approach, optimal (enumerate split points directly), runs in O(n²) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (build every string and evaluate it) up.

Problem

You are given a string expression of the form "<num1>+<num2>", where both numbers are positive integers.

Insert exactly one '(' and one ')' so that the result is still a valid expression: the '(' must be placed somewhere to the left of the '+' (possibly before the first digit) and the ')' somewhere to the right of it (possibly after the last digit). A number written directly next to a parenthesis is multiplied with the parenthesised group, so "3(4+5)6" means 3 * (4 + 5) * 6.

Return the expression with parentheses that has the smallest possible value. If several placements share that value, any of them is accepted.

Examples

Example 1

Input
expression = "12+34"
Output
"1(2+3)4"
Why
This reads 1 * (2 + 3) * 4 = 20. The other placements give 46, 60 and 36.

Example 2

Input
expression = "5+7"
Output
"(5+7)"
Why
Each side has one digit, so the parentheses can only wrap the whole expression.

Example 3

Input
expression = "999+1"
Output
"9(99+1)"
Why
9 * (99 + 1) = 900, smaller than (999+1) = 1000 and 99 * (9 + 1) = 990.

Constraints

  • 3 <= expression.length <= 10
  • expression has the form "<num1>+<num2>", where both numbers use digits 1–9 only.
  • The original expression and every possible placement evaluate to values that fit in a 32-bit signed integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (build every string and evaluate it)O(n³)O(n)
Optimal (enumerate split points directly)O(n²)O(n)

1Brute force (build every string and evaluate it)

TimeO(n³)O(n²) placements, each building and scanning an O(n) string.
SpaceO(n)One candidate string at a time.

Generate each candidate string with parentheses inserted, then evaluate it with a small parser that reads numbers and treats a number touching a parenthesis as a multiplication. Keep the candidate with the smallest value.

  1. Let p be the index of '+'. For each i in 0..p-1 and each j in p+2..n, build s[0..i) + "(" + s[i..j) + ")" + s[j..n).
  2. Evaluate it: read the number before '(' (default 1), the two numbers inside, and the number after ')' (default 1).
  3. Value = before * (left + right) * after; keep the candidate if it is strictly smaller than the best so far.
class Solution {
    public String minimizeResult(String expression) {
        int n = expression.length(), p = expression.indexOf('+');
        String best = "";
        long bestVal = Long.MAX_VALUE;
        for (int i = 0; i < p; i++)
            for (int j = p + 2; j <= n; j++) {
                String cand = expression.substring(0, i) + "(" + expression.substring(i, j) + ")" + expression.substring(j);
                long v = eval(cand);
                if (v < bestVal) {
                    bestVal = v;
                    best = cand;
                }
            }
        return best;
    }

    private long eval(String s) {
        long[] nums = new long[4];
        nums[0] = 1;
        nums[3] = 1;
        int part = 0;
        long cur = 0;
        boolean has = false;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                cur = cur * 10 + (c - '0');
                has = true;
            } else {
                if (has) nums[part] = cur;
                cur = 0;
                has = false;
                part++;
            }
        }
        if (has) nums[part] = cur;
        return nums[0] * (nums[1] + nums[2]) * nums[3];
    }
}

2Optimal (enumerate split points directly)

TimeO(n²)O(n²) split pairs; with at most 10 characters each parse is effectively constant.
SpaceO(n)Substrings and the final answer.

Split the two numbers instead of building strings. For a '(' before index i of the left number and a ')' after index j of the right number, the value is prefix * (leftInner + rightInner) * suffix, with an empty prefix or suffix counting as 1. Compute the four parts from substrings, track the minimum, and build only the winning string at the end.

  1. Let a = expression[0..p) and b = expression[p+1..n).
  2. For i in 0..len(a)-1 and j in 1..len(b): pre = i == 0 ? 1 : a[0..i), x = a[i..), y = b[0..j), suf = j == len(b) ? 1 : b[j..).
  3. Value = pre * (x + y) * suf; remember (i, j) when it is strictly smaller.
  4. Return a[0..i) + "(" + a[i..) + "+" + b[0..j) + ")" + b[j..) for the best pair.
class Solution {
    public String minimizeResult(String expression) {
        int p = expression.indexOf('+');
        String a = expression.substring(0, p), b = expression.substring(p + 1);
        long best = Long.MAX_VALUE;
        int bi = 0, bj = b.length();
        for (int i = 0; i < a.length(); i++)
            for (int j = 1; j <= b.length(); j++) {
                long pre = i == 0 ? 1 : Long.parseLong(a.substring(0, i));
                long x = Long.parseLong(a.substring(i));
                long y = Long.parseLong(b.substring(0, j));
                long suf = j == b.length() ? 1 : Long.parseLong(b.substring(j));
                long v = pre * (x + y) * suf;
                if (v < best) {
                    best = v;
                    bi = i;
                    bj = j;
                }
            }
        return a.substring(0, bi) + "(" + a.substring(bi) + "+" + b.substring(0, bj) + ")" + b.substring(bj);
    }
}

Edge cases to test

  • Single-digit numbers on both sides (only one placement)
  • Wrapping the whole expression is the best choice
  • Several placements tie for the minimum (any of them is accepted)

Hints

Hint 1

The '(' goes somewhere in the left number and the ')' goes somewhere in the right number. How many pairs of positions is that?

Hint 2

For a placement, the left number splits into a prefix multiplier and the part inside the parentheses; the right number splits into the part inside and a suffix multiplier. An empty multiplier counts as 1.

FAQ

What is the best time complexity for Minimize Result by Adding Parentheses to Expression?

Optimal (enumerate split points directly) runs in O(n²) time and O(n) extra space. O(n²) split pairs; with at most 10 characters each parse is effectively constant.

Which pattern does Minimize Result by Adding Parentheses to Expression use?

It is a arrays & hashing problem that uses the candidate generation pattern. Other problems with the same pattern: Find the Closest Palindrome.

Is there a brute force solution for Minimize Result by Adding Parentheses to Expression?

Yes. Brute force (build every string and evaluate it) takes O(n³) time and O(n) space. Generate each candidate string with parentheses inserted, then evaluate it with a small parser that reads numbers and treats a number touching a parenthesis as a multiplication.

Which edge cases should I test for Minimize Result by Adding Parentheses to Expression?

Single-digit numbers on both sides (only one placement); Wrapping the whole expression is the best choice; Several placements tie for the minimum (any of them is accepted).