Scale Engineer

Remove Outermost Parentheses

Easy
#0975Time: O(N), where N is the length of the string. We iterate through the string once. The `substring` operation in Java takes time proportional to the length of the substring. Since the sum of lengths of all substrings is N, the total time complexity remains O(N).Space: O(N), where N is the length of the input string. This is required for the `StringBuilder` that stores the result, which can have a length up to N-2.
Data structures
StringStack

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly follows the problem's definition. It first identifies the primitive components of the input string by tracking the balance of parentheses. Once a primitive component is identified, its outermost parentheses are removed, and the inner content is appended to the result.

Algorithm

  • Initialize a StringBuilder result to store the final string.
  • Initialize an integer balance = 0 to track the nesting level of parentheses.
  • Initialize an integer start = 0 to mark the beginning of the current primitive component.
  • Iterate through the input string s from i = 0 to s.length() - 1.
  • If s.charAt(i) == '(', increment balance.
  • If s.charAt(i) == ')', decrement balance.
  • If balance == 0, we have found a complete primitive component from index start to i.
  • Append the inner part of this component (s.substring(start + 1, i)) to the result.
  • Update start to i + 1 to mark the beginning of the next component.
  • After the loop, return result.toString().

Walkthrough

We iterate through the string while maintaining a balance counter. The counter is incremented for an opening parenthesis ( and decremented for a closing one ). A primitive string is a valid parentheses string that cannot be split into two non-empty valid parentheses strings. This means that for a primitive string, the balance counter only returns to zero at the very end. Therefore, whenever our balance counter, which starts at zero, returns to zero during the iteration, we have identified the end of a primitive component. We then extract this component, remove its first and last characters (the outermost parentheses), and append the remaining part to our result. We then reset the starting point for the next primitive component and continue until the entire string is processed.

class Solution {    public String removeOuterParentheses(String s) {        StringBuilder result = new StringBuilder();        int balance = 0;        int start = 0;        for (int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            if (c == '(') {                balance++;            } else {                balance--;            }            if (balance == 0) {                // Found a primitive component from start to i                // Append the content inside the outermost parentheses                result.append(s.substring(start + 1, i));                // Update start for the next primitive component                start = i + 1;            }        }        return result.toString();    }}

Complexity

Time

O(N), where N is the length of the string. We iterate through the string once. The `substring` operation in Java takes time proportional to the length of the substring. Since the sum of lengths of all substrings is N, the total time complexity remains O(N).

Space

O(N), where N is the length of the input string. This is required for the `StringBuilder` that stores the result, which can have a length up to N-2.

Trade-offs

Pros

  • The logic is a direct translation of the problem statement, making it relatively easy to understand and implement.

Cons

  • Involves creating intermediate substrings, which can be less memory-efficient and slightly slower due to object creation overhead compared to a single-pass approach.

Solutions

class Solution {public  String removeOuterParentheses(String s) {    StringBuilder ans = new StringBuilder();    int cnt = 0;    for (int i = 0; i < s.length(); ++i) {      char c = s.charAt(i);      if (c == '(') {        if (++cnt > 1) {          ans.append(c);        }      } else {        if (--cnt > 0) {          ans.append(c);        }      }    }    return ans.toString();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem