D
DevExCode
DevExCode

713993. Redundant Parenthesis

Hard

Redundant Parenthesis

Slug: redundant-parenthesis--170647 Difficulty: Hard Id: 713993 Topic Tags: Strings, Stack, Data Structures Company Tags: Oracle

Summary

The problem is about removing redundant parentheses from a given expression. The expression can contain any valid mathematical operation (e.g., addition, subtraction, multiplication, division) and parentheses. A pair of parentheses is considered redundant if the part within the parentheses does not affect the final result.

Detailed Explanation

To solve this problem, we'll use a stack to keep track of the opening and closing parentheses. We'll iterate through the expression from left to right, and for each character:

  • If the character is an opening parenthesis, push it onto the stack.
  • If the character is a closing parenthesis, check if the stack is empty or not. If the stack is not empty, pop the top element (which should be an opening parenthesis) from the stack. If the stack is empty, it means there's no matching opening parenthesis for this closing parenthesis, so we'll ignore it.
  • If the character is neither an opening nor a closing parenthesis, we'll ignore it.

Once we've processed the entire expression, if the stack is not empty, it means there are redundant parentheses left. We'll then pop all the elements from the stack and add them to the result string (each element will be an opening or closing parenthesis).

Time complexity: O(n), where n is the length of the input expression. Space complexity: O(n), as in the worst-case scenario, we might need to store all parentheses in the stack.

Here's a step-by-step breakdown of the solution:

  1. Initialize an empty string result and an empty stack s.
  2. Iterate through the expression from left to right:
    • If the current character is an opening parenthesis, push it onto s.
    • If the current character is a closing parenthesis, check if s is empty or not.
      • If s is not empty, pop the top element (which should be an opening parenthesis) from s.
      • If s is empty, ignore the closing parenthesis.
    • If the current character is neither an opening nor a closing parenthesis, ignore it.
  3. Once you've processed the entire expression:
    • If s is not empty, pop all elements from s and add them to result. Each element will be an opening or closing parenthesis.

Optimized Solutions

Java

View on GeeksforGeeks
public class Solution {
    public String removeRedundantParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder result = new StringBuilder();
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    result.append(c);
                }
            } else {
                result.append(c);
            }
        }
        
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        
        return result.toString();
    }
}

DevExCode

Master coding interviews with Leetcode, system design, TechBit, QuickLearn, DevTips, Tech Battles, and career services.

© 2026 DevExCode. All rights reserved.