Leetcode problem 133 - Minimum Number of Arrows to Burst Balloons

A valid parentheses string is either empty “”, “(“ + A + “)”, or A + B, where A and B are valid parentheses strings, and + represents string concatenation.

For example, “”, “()”, “(())()”, and “(()(()))” are all valid parentheses strings. A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + … + Pk, where Pi are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

Example 1:

Input: s = “(()())(())” Output: “()()()” Explanation: The input string is “(()())(())”, with primitive decomposition “(()())” + “(())”. After removing outer parentheses of each part, this is “()()” + “()” = “()()()”. Example 2:

Input: s = “(()())(())(()(()))” Output: “()()()()(())” Explanation: The input string is “(()())(())(()(()))”, with primitive decomposition “(()())” + “(())” + “(()(()))”. After removing outer parentheses of each part, this is “()()” + “()” + “()(())” = “()()()()(())”. Example 3:

Input: s = “()()” Output: “” Explanation: The input string is “()()”, with primitive decomposition “()” + “()”. After removing outer parentheses of each part, this is “” + “” = “”.

Constraints:

1 <= s.length <= 105 s[i] is either ‘(‘ or ‘)’. s is a valid parentheses string.

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function (s) {
  let count = 0;
  let output = "";

  for (let char of s) {
    if (char === "(") {
      if (count) {
        output += char;
      }
      count++;
    } else {
      count--;
      if (count) {
        output += char;
      }
    }
  }
  return output;
};

The given code iterates through each character of the string s exactly once, making the time complexity O(n), where n is the length of the string s.

Space complexity is O(1). The code utilizes a constant amount of space regardless of the length of the input string. There are only two variables used, count and output, and no additional memory is allocated based on the size of the input string. Therefore, the space complexity is constant, denoted as O(1).