Expression contains redundant bracket or not

The problem, simply

You get a valid math sentence with letters, the signs + - * /, and round brackets. Say true if some pair of brackets is redundant, and false if every pair is doing a job.

A pair is redundant when there is no sign directly inside it. Examples: (), (a), and the outer pair of ((a+b)). Signs that are inside a deeper pair do not count for the outer pair.

This check does not look at "times before plus". a+(b*c) counts as fine here, because its brackets hold a sign.

A story to remember it

Picture it

Examples

Way 1: the simple way

For every opening bracket, walk right until its matching closing bracket. On the way, keep a depth counter. If you see a sign while the depth is 1 (directly inside this pair), the pair is useful. If you reach the match without one, it is redundant.

1. For each i where s[i] == '(', set depth = 1.
2. Move j right. ( adds one to depth, ) takes one away, and a sign at depth 1 marks the pair as useful.
3. Stop when depth hits 0. If no sign was marked, return true.

class Solution {
    public boolean hasRedundant(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != '(') continue;
            int depth = 1;
            boolean useful = false;
            for (int j = i + 1; j < n && depth > 0; j++) {
                char c = s.charAt(j);
                if (c == '(') depth++;
                else if (c == ')') depth--;
                else if (depth == 1 && "+-*/".indexOf(c) >= 0) useful = true;
            }
            if (!useful) return true;     // nothing happens in this box
        }
        return false;
    }
}

How long it takes: each opening bracket may scan to the end, so O(n^2) for deep nesting. Extra room: a few counters, O(1).

Way 2: the clever way

Use a pile, a stack, so each closing bracket can look at exactly its own box.

1. Read the sentence left to right. Push every character except ).
2. On ), pop until you reach (. While popping, note whether any popped character is a sign.
3. Pop the ( too. If no sign was popped, this pair is redundant: return true.
4. If the whole sentence is read, return false.

Why does this only see its own level? Any deeper pair was already popped completely when its own ) arrived, signs and all. What is left between the top and the nearest ( belongs to this box only.

class Solution {
    public boolean hasRedundant(String s) {
        Deque<Character> pile = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c != ')') {
                pile.push(c);
                continue;
            }
            boolean useful = false;
            while (pile.peek() != '(') {
                char top = pile.pop();
                if (top == '+' || top == '-' || top == '*' || top == '/') useful = true;
            }
            pile.pop();                    // the matching (
            if (!useful) return true;      // an empty or single item box
        }
        return false;
    }
}

How long it takes: every character is pushed once and popped at most once, O(n). Extra room: the pile, O(n).

Watch out for

• Empty brackets () must count as redundant. The pop loop runs zero times, useful stays false, and that is correct.
• A pair around one long name like (abc) is redundant too. Letters alone are never a sign.
• If the input can be unbalanced, guard pile.peek() against an empty pile.
• Ask whether "redundant" should consider precedence. In this classic version it does not.

What interviewers ask next

• Use less memory. Push only ( and signs, not letters. On ), if the top is (, the box had no sign.
• Remove all unneeded brackets while keeping the value the same. Now precedence matters: a pair around b*c after + can go, but a pair around b+c after * cannot. Track the weakest sign inside each pair and compare it with the signs just outside.
• Count the redundant pairs instead of stopping at the first one. Keep going and add one each time instead of returning.
• What if the input has [ and { too? Push any opener, pop until the matching opener, and also check the kinds match.

Remember this

Grown-up words: the gift boxes are bracket pairs, "doing a job" means containing an operator at its own nesting level, and the pile is a stack that matches each ) with its (.