Java Solution: Redundant Parenthesis Detection O(N)

Problem

Given a string of balanced expression s, check if it contains a redundant parenthesis or not. A set of parenthesis are redundant if the same sub-expression is surrounded by unnecessary or multiple brackets.
Note: Expression may contain + , — , *, and / operators. Given expression is valid and there are no white spaces present.

Examples:

Input: s = "((a+b))"
Output: true
Explanation: ((a+b)) can reduced to (a+b).

Input: s = "(a+(b)/c)"
Output: true
Explanation: (a+(b)/c) can reduced to (a+b/c) because b is surrounded by () which is redundant.

Input: s = "(a+b+(c+d))"
Output: false
Explanation:(a+b+(c+d)) doesn't have any redundant or multiple brackets.

Constraints:

1 ≤ |s| ≤10^5

Approach

In a naive approach, we might treat the string as a sequence of sub-expressions. The goal is to isolate every pair of matching parentheses ( ... ) and check the contents inside them.

The Algorithm

1. Iterate through the string to find an opening bracket (.
2. Scan forward to find the matching closing bracket ).
3. Extract the substring between them. 4.Scan that substring:
   • Does it contain an operator (+, -, *, /)?
   • If No, the brackets are redundant (e.g., (a)).
   • If Yes, checking isn’t done yet — we have to ensure we didn’t just capture a nested redundant pair like ((a+b)).

Why this is inefficient

Complexity: finding a matching bracket and extracting substrings repeatedly forces us to scan the string multiple times. In the worst case (deeply nested brackets), this approaches O(N²) time complexity.
Messy Logic: Handling nested structures like ((a+b)*(c-d)) without a stack requires complex index tracking to ensure you are looking at the correct matching bracket, not just the next one you see.

We need a way to process the expression in a single pass (O(N)). Since the problem involves nested structures (brackets inside brackets), the Last-In-First-Out (LIFO) property of a Stack is the perfect tool.

Instead of scanning forward to find the end of a bracket pair, we can process characters as they come and “resolve” them when we hit a closing bracket ).

The Optimal Stack Approach

We treat the Stack as a “holding area” for the parts of the expression we haven’t finished evaluating yet.

1. Iterate through the expression.
2. If we see an open bracket ( or an operator: Push it onto the stack. These are the components that might be part of a valid sub-expression.
3. If we see a closing bracket ): This is our trigger. It means a sub-expression has just ended. We need to check if that sub-expression was "useful."

4.Start popping from the stack until we hit the matching (.
While popping, did we encounter an operator?
Yes: The brackets enclosed an operation (e.g., (a+b)), so they were necessary.
No: The brackets enclosed nothing of value (e.g., (a) or ()), so they are Redundant.

Time and Space Complexity

Time O(N): Single pass iteration, each element pushed/popped once.

Space O(N): Stack acts as a buffer; worst case stores all characters.

Code

class Solution {
    public static boolean checkRedundancy(String s) {
        // code here
        if (s == null || s.length() == 0) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            boolean isRedundant = true;
            if (ch == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    char topChar = stack.pop();
                    if (isValidOperator(topChar)) {
                        isRedundant = false;
                    }
                }
                if (!stack.isEmpty()) {
                    stack.pop();
                }
                if (isRedundant) {
                    return true;
                }
            }
            else if (isValidChar(ch)) {
                stack.push(ch);
            }
        }
        return false;
    }

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

    private static boolean isValidChar(char ch) {
        return isValidOperator(ch) || ch == '(';
    }
}