Java Solution: Redundant Parenthesis Detection O(N)

Source: Dev.to

Problem

Given a string s representing a balanced expression, determine whether it contains any redundant parentheses.
A pair of parentheses is redundant if the same sub‑expression is surrounded by unnecessary or multiple brackets.

Examples

• s = "((a+b))" → redundant
• s = "(a+(b)/c)" → not redundant
• s = "(a+b+(c+d))" → not redundant

Constraints: 1 ≤ |s| ≤ 10^5

Naïve Approach

1. Iterate through the string to find an opening bracket (.
2. Scan forward to locate the matching closing bracket ).
3. Extract the substring between them.
4. Check whether the substring contains an operator (+, -, *, /).
   • If no operator is present, the brackets are redundant (e.g., (a)).
   • If an operator is present, further checks are needed to avoid counting nested redundant pairs like ((a+b)).

This method may require scanning the same characters many times, leading to O(N²) time in the worst case (deeply nested brackets).

Efficient O(N) Solution Using a Stack

The expression contains nested structures, which naturally fit a Last‑In‑First‑Out (LIFO) data structure. By processing the characters sequentially and using a stack, we can detect redundancy in a single pass.

Algorithm

1. Initialise an empty stack.
2. Iterate over each character ch in the string:
   • If ch is an opening bracket ( or an operator (+, -, *, /), push it onto the stack.
   • If ch is a closing bracket ):
     1. Pop elements from the stack until an opening bracket ( is encountered.
     2. While popping, check whether any popped character is an operator.
        • If no operator is found, the current pair of parentheses is redundant → return true.
     3. Discard the matching ( from the stack.
3. If the loop finishes without detecting redundancy, return false.

Complexity

• Time: O(N) – each character is pushed and popped at most once.
• Space: O(N) – in the worst case the stack holds all characters of the expression.

Reference Implementation (Java)

import java.util.Stack;

class Solution {
    public static boolean checkRedundancy(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }

        Stack stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (ch == ')') {
                boolean hasOperator = false;

                // Pop until the matching '('
                while (!stack.isEmpty() && stack.peek() != '(') {
                    char top = stack.pop();
                    if (isOperator(top)) {
                        hasOperator = true;
                    }
                }

                // Remove the '(' if present
                if (!stack.isEmpty()) {
                    stack.pop();
                }

                // No operator inside the parentheses → redundant
                if (!hasOperator) {
                    return true;
                }
            } else if (isOperator(ch) || ch == '(') {
                // Only push operators and '('; operands are irrelevant for redundancy check
                stack.push(ch);
            }
        }

        return false;
    }

    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }
}

The method checkRedundancy returns true if the input expression contains any redundant parentheses, otherwise false.