BACK TO ALL POSTS

RCP #1: Balanced Parentheses

May 2nd, 2019 • 10 min read

As a way to keep constant writing motivation, I have decided to do an occasional sharing of random coding problems that I have found to be interesting. I hope this would also be a chance for me to review and enhance my understanding of the logic behind these questions.

For this first post, we will look into a quite common coding problem that plenty of developers would know. Then, we will also explore some problems extending from it.

1. Check if sequence of parentheses is balanced

Given a string containing just the two characters ( and ), determine if the input string is a balanced sequence of parantheses.

Examples:

Input: "(())"
Output: true
Input: "()()"
Output: true
Input: "()("
Output: false

For this problem, we must identify these properties of a balanced sequence:

  • The right bracket will match with the nearest unmatched left bracket in front of it, and vice versa.
  • The number of left brackets is the same as the number of right brackets

Hence, when we iterate the string from left to right, it will only be unbalanced under these 2 cases:

  • A right bracket does not manage to find an unmatched left bracket in front of it e.g. ()())
  • There are more left brackets than right brackets e.g. ()()(() at the end of the iteration

From these points, what we can do is to iterate through the string while keeping a counter of the number of unmatched left brackets so far. Every time we encounter a right bracket, we will decrease the counter by 1 since the nearest left bracket will be matched and negated by this right bracket. The string is considered to be unbalanced if the counter is negative at any moment or the counter is positive at the end of the iteration.

// Time: O(n)
// Space: O(1)
function isBalanced(str: string): boolean {
  let leftBracketsCounter = 0;

  for (const c of str) {
    if (c === "(") {
      leftBracketsCounter++;
    } else {
      leftBracketsCounter--;
      if (leftBracketsCounter < 0) {
        return false;
      }
    }
  }

  return leftBracketsCounter === 0;
}

2. Generate all balanced sequences of parentheses

Given N pairs of parentheses, write a function to generate all balanced sequences.

Example:

Input: 3
Output:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

From the points we deduced in the first problem, whenever we are building a potential candidate for a balanced sequence, a right bracket can only be appended to the sequence only if the number of right brackets so far is less than that of left brackets.

Therefore, by applying Backtracking, we can recursively build each of the balanced sequences while keeping two counters for the number of left brackets and right brackets so far in the sequence to ensure that the condition is met.

function generateBalancedSequences(n: number): string[] {
  if (n === 0) {
    return [];
  }

  const res: string[] = [];
  backtrack([], res, 0, 0, n);

  return res;
}

function backtrack(
  arr: string[],
  res: string[],
  leftCount: number,
  rightCount: number,
  maxCount: number,
): void {
  // A balanced sequence is completed
  if (leftCount === maxCount && rightCount === maxCount) {
    res.push(arr.join(""));
    return;
  }

  // Add left bracket first if it's still available
  if (leftCount < maxCount) {
    arr.push("(");
    driver(arr, res, leftCount + 1, rightCount, maxCount);
    arr.pop();
  }

  // Only add a right bracket if number of right brackets is less than that of left brackets
  if (rightCount < leftCount) {
    arr.push(")");
    driver(arr, res, leftCount, rightCount + 1, maxCount);
    arr.pop();
  }
}

3. The longest balanced sequence of parentheses

Given a string containing just the two characters ( and ), find the length of the longest balanced sequence of parentheses substring.

Examples:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

A brute-force approach to this problem can be achieved by reusing the first problem. For every substring in the given string, we will check if the substring is a balanced sequence and compare its length to the maximum length so far.

function isBalanced(str: string): boolean {
  // Refer to Problem 1
  ...
}

// Time: O(n ** 3)
// Space: O(1)
function longestBalancedSequence(str: string): number {
  let max = 0;

  for (let i = 0; i < str.length; i++) {
    for (let j = i; j < str.length; j++) {
      const substring = str.substr(i, j - i + 1);
      if (isBalanced(substring)) {
        max = Math.max(max, substring.length);
      }
    }
  }

  return max;
}

For the brute-force solution, we realize that we did a lot of overlapping works to keep track of the counter of unmatched left brackets for every substring. To achieve a solution with better time complexity, we must try to remove these overlapping calculations.

One solution is to use Dynamic Programming. We will have a cache array where cache[i] stores the length of the longest balanced sequence ending at i. If str[i] is (, cache[i] will be 0. If str[i] is ), we can split into 2 main cases based on what is the character in str[i - 1]:

  • When str[i - 1] is ( i.e ...(), cache[i] will be cache[i - 2] + 2

  • When str[i - 1] is ) i.e ...)), if cache[i - 1] is larger than 0, the string will have this form ...X(...)) where X is the character at index i - 1 - cache[i - 1] before the start index of longest balanced sequence ending at i - 1.

    If X is ), cache[i] will be 0.

    Else if X is (, cache[i] will be cache[i - 1] + 2 + cache[i - cache[i - 1] - 2]

The result will be the maximum element in the cache array.

// Time: O(n)
// Space: O(n)
function longestBalancedSequence(str: string): number {
  const cache: number[] = [...Array(str.length)].fill(0);

  for (let i = 1; i < str.length; i++) {
    // Ignore left bracket char
    if (str[i] === "(") {
      continue;
    }
    // Previous char is left bracket
    else if (str[i - 1] === "(") {
      cache[i] = 2 + (i > 1 ? cache[i - 2] : 0);
    }
    // Previous char is right bracket and contains a balanced sequence
    else if (cache[i - 1] > 0) {
      const nearestIndex = i - 1 - cache[i - 1];

      // If nearest index is left bracket
      if (nearestIndex >= 0 && str[nearestIndex] === "(") {
        cache[i] =
          2 +
          cache[i - 1] +
          (nearestIndex > 1 ? cache[nearestIndex - 1] : 0);
      }
    }
  }

  return cache.reduce(
    (max, length) => Math.max(max, length),
    0,
  );
}

There exists another approach that helps us achieve O(1) space complexity while keeping the time complexity at O(n).

To understand this approach, we need to revisit the findings we did from the first problem. A balanced sequence will have the same amount of left brackets and right brackets. If we iterate from left to right through the string and the number of right brackets is more than that of left brackets at any moment, the sequence is guaranteed to be unbalanced.

Hence, what we can do is to iterate from left to right through the string while having 2 Counters for the number of left brackets and right brackets so far. Whenever we encounter a right bracket:

  • If the sequence now has more right brackets than left brackets, we can confirm that this current sequence is unbalanced and refresh the sequence starting from the next character.
  • If the sequence now has the same amount of left brackets and right brackets, the sequence is balanced and we update the maximum length if needed.

However, if we just iterate from left to right through the string, we will miss cases when a section has more left brackets than right brackets like ()((()). For this case, if we just iterate from left to right, the result we get will be 2 while the actual correct maximum length is 4.

Therefore, we will need to iterate both left-to-right and right-to-left so we can check for all the possible balanced sequences.

  • ()((()): This will need to be iterated from right to left
  • (()))(): This will need to be iterated from left to right
// Time: O(n)
// Space: O(1)
function longestBalancedSequence(str: string): number {
  let leftBracketsCount = 0;
  let rightBracketsCount = 0;
  let max = 0;

  for (let i = 0; i < str.length; i++) {
    if (str[i] === "(") {
      leftBracketsCount++;
    } else {
      rightBracketsCount++;
    }

    if (leftBracketsCount === rightBracketsCount) {
      max = Math.max(leftBracketsCount * 2);
    } else if (leftBracketsCount < rightBracketsCount) {
      leftBracketsCount = 0;
      rightBracketsCount = 0;
    }
  }

  leftBracketsCount = 0;
  rightBracketsCount = 0;

  for (let i = str.length; i >= 0; i--) {
    if (str[i] === ")") {
      rightBracketsCount++;
    } else {
      leftBracketsCount++;
    }

    if (leftBracketsCount === rightBracketsCount) {
      max = Math.max(leftBracketsCount * 2);
    } else if (leftBracketsCount > rightBracketsCount) {
      leftBracketsCount = 0;
      rightBracketsCount = 0;
    }
  }

  return max;
}

4. Check if the sequence of parentheses with wildcards is balanced

Given a string containing only three types of characters: (, ) and *, write a function to check whether this string is a balanced sequence. * could be treated as a single right parenthesis ) or a single left parenthesis ( or an empty string.

Examples:

Input: "()"
Output: true
Input: "(*)"
Output: true
Input: "(*))"
Output: true

For this problem, a brute-force approach will be constructing all possible strings by replacing each wildcard with (, ) and empty string. Then, we will check if there exists a balanced sequence among those candidates. The time complexity for the worst case where every character in the string is a wildcard will be O(n * (3 ** n))

To improve the time complexity, we can approach this problem, in the same manner, we did for the original problem. When we iterate from left to right through the string, if we encounter a right bracket:

  • If there is an available left bracket without being matched yet, it will be matched and negated by this right bracket
  • If there are no available left brackets but there is an available wildcard, it will be turned into a left bracket and matched with this right bracket.
  • If there are no available left brackets or wildcards, the string is guaranteed to be unbalanced.

At the end of the iteration, if there are still unmatched left brackets, we will then attempt to match each left bracket to an available wildcard with the condition that the wildcard's position needs to be after the position of left bracket. The string is balanced if all left brackets are successfully matched.

Since the position of each left bracket and wildcard matters, we will use 2 Stacks to keep track of all unmatched left brackets and available wildcards instead of using a counter like the original problem.

// Time: O(n)
// Space: O(n)
function isBalancedSequence(str: string): boolean {
  const leftBracketsStack: number[] = [];
  const wildcardsStack: number[] = [];

  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    if (char === "(") {
      leftBracketsStack.push(i);
    } else if (char === "*") {
      wildcardsStack.push(i);
    } else {
      if (leftBracketsStack.length > 0) {
        leftBracketsStack.pop();
      } else if (wildcardsStack.length > 0) {
        wildcardsStack.pop();
      } else {
        return false;
      }
    }
  }

  while (
    leftBracketsStack.length > 0 &&
    wildcardsStack.length > 0
  ) {
    const leftBracketIndex = leftBracketsStack.pop();
    const wildcardIndex = wildcardsStack.pop();
    if (leftBracketIndex > wildcardIndex) {
      return false;
    }
  }

  return leftBracketsStack.length === 0;
}

Another approach that will let us achieve O(1) space complexity while keeping the time complexity at O(n) is to applying Greedy Algorithm.

For the original problem, when we iterate through the string, the indicator for us to know if the string is unbalanced is the number of unmatched left brackets. If the number is negative at any moment or positive at the end of the iteration, the string will be unbalanced.

Now for every time we encounter a wildcard, as the wildcard can only be (, ) or an empty string, instead of incrementing or decrementing the counter, it will expand the continuous range of integers that the counter can be.

For example, the string (*) will create this sequence of ranges for the counter when we iterate through the string [1, 1], [0, 2], [0, 1].

So in order to check if the string can be a balanced sequence, we will just keep track of the lower limit and upper limit of the possible range for the counter. If the upper limit is negative at any moment or the lower limit is positive at the end of the iteration, the string will always be unbalanced.

// Time: O(n)
// Space: O(1)
function isBalancedSequence(str: string): boolean {
  let low = 0;
  let high = 0;

  for (const c of str) {
    low += c === "(" ? 1 : -1;
    high += c === ")" ? -1 : 1;
    if (high < 0) {
      return false;
    }
    low = Math.max(low, 0);
  }

  return low === 0;
}

Final Thoughts

After going through the above problems, I hope you now have a better understanding of how to tackle these types of questions about balanced parentheses.

The most important factor here is to recognize the requirements for identifying a balanced sequence. From that point, it will be just about optimizing the time complexity by reducing the overlapping calculations or optimizing the space complexity by simplifying how we keep track of the condition for a balanced sequence as we are scanning the string. 🙌

So until the next sharing comes, see you when I see you! ✌️

Algorithm
Random Coding Problem