Max Score Brackets

Anonymous User

157

I was asked this question in a phone interview recently. posting it here if it helps anyone :)

Question:
Given a string of "(" and ")" brackets. return the maximum score where score is incremented based on indexes (j-i) each time you find a balanced pair.

My Intuition:

calc maximum score by matching brackets furthest away
the given brackets may be imbalanced, so it may be okay if all brackets are not used to calculate the score.
the solution is straightforward if brackets are balanced. the tricky part is how to pick them when they are imbalanced.

Here is the solution I implemented (using 2-pointer approach).

Please let me know if there is any case I missed. Thanks!!

public class Solution {
    // time: O(n)
    // space: O(1)
    public static int maxScoreBrackets(String s) {
        int left = 0, right = s.length() - 1;
        int totalScore = 0;

        while (left < right) {
            // Move left pointer to the next '('
            while (left < right && s.charAt(left) != '(') {
                left++;
            }
            // Move right pointer to the next ')'
            while (left < right && s.charAt(right) != ')') {
                right--;
            }
            // If valid pair found, add score and move pointers
            if (left < right) {
                totalScore += (right - left);  // Add the score for this matched pair
                left++;  // Move past the matched '('
                right--; // Move past the matched ')'
            }
        }
        return totalScore;
    }

    public static void main(String[] args) {
        System.out.println("((())) , out: " + maxScoreBrackets("((()))") + ", expected: " + 9);
        System.out.println("((() , out: " + maxScoreBrackets("((()") + ", expected: " + 3);
        System.out.println("())) , out: " + maxScoreBrackets("()))") + ", expected: " + 3);
        System.out.println("()() , out: " + maxScoreBrackets("()()") + ", expected: " + 3);
        System.out.println("()()() , out: " + maxScoreBrackets("()()()") + ", expected: " + 6);
        System.out.println("(()()) , out: " + maxScoreBrackets("(()())") + ", expected: " + 8);
        System.out.println(")()() , out: " + maxScoreBrackets(")()()") + ", expected: " + 3);
        System.out.println("()()) , out: " + maxScoreBrackets("()())") + ", expected: " + 5   );
        System.out.println("(())) , out: " + maxScoreBrackets("(()))") + ", expected: 4"); // Extra closing bracket at the end
        System.out.println("((()) , out: " + maxScoreBrackets("((())") + ", expected: 4"); // Extra opening bracket at the start
        System.out.println("((( , out: " + maxScoreBrackets("(((") + ", expected: 0"); // Only opening brackets
        System.out.println("))) , out: " + maxScoreBrackets(")))") + ", expected: 0"); // Only closing brackets
        System.out.println("())( , out: " + maxScoreBrackets("())(") + ", expected: 2"); // Only one valid pair "()"
        System.out.println(")()( , out: " + maxScoreBrackets(")()(") + ", expected: 1"); // Ignore unmatched ')'
    }

}

Comments (0)