Build confidence with an intuition-first walkthrough focused on stack fundamentals.
A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.
"", "()", "(())()", 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 <= 105s[i] is either '(' or ')'.s is a valid parentheses string.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Stack
"(()())(())"
"(()())(())(()(()))"
"()()"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1021: Remove Outermost Parentheses
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();
}
}
// Accepted solution for LeetCode #1021: Remove Outermost Parentheses
func removeOuterParentheses(s string) string {
ans := []rune{}
cnt := 0
for _, c := range s {
if c == '(' {
cnt++
if cnt > 1 {
ans = append(ans, c)
}
} else {
cnt--
if cnt > 0 {
ans = append(ans, c)
}
}
}
return string(ans)
}
# Accepted solution for LeetCode #1021: Remove Outermost Parentheses
class Solution:
def removeOuterParentheses(self, s: str) -> str:
ans = []
cnt = 0
for c in s:
if c == '(':
cnt += 1
if cnt > 1:
ans.append(c)
else:
cnt -= 1
if cnt > 0:
ans.append(c)
return ''.join(ans)
// Accepted solution for LeetCode #1021: Remove Outermost Parentheses
impl Solution {
pub fn remove_outer_parentheses(s: String) -> String {
let mut res = String::new();
let mut depth = 0;
for c in s.chars() {
if c == '(' {
depth += 1;
}
if depth != 1 {
res.push(c);
}
if c == ')' {
depth -= 1;
}
}
res
}
}
// Accepted solution for LeetCode #1021: Remove Outermost Parentheses
function removeOuterParentheses(s: string): string {
let res = '';
let depth = 0;
for (const c of s) {
if (c === '(') {
depth++;
}
if (depth !== 1) {
res += c;
}
if (c === ')') {
depth--;
}
}
return res;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.