Stack Parenthesis

---

The Philosophy of "Parenthesis Tasks"

• A "Forced" Category: "Parenthesis" is not an official category; we are forcing this classification. Most of these tasks are derived from real-life programming needs (like LRU cache, git commits, etc.), and we use this umbrella term to group them.

  • TL;DR: It's a real-life motivated task.

• Recursive Definition: A parenthesis is used to enclose an object, often to increase evaluation priority.

  • new_object = (old_object)
  • new_object = (old_object1)(old_object2)

• The Umbrella Logic: Since this is a "forced" topic, we will use a "forced" solution technique. We will try to develop a unified way to view these problems.

---

Rethinking the Tool: The Stack

• Don't Call it "Stack": "Stack" implies something vertical. In these tasks, think of it as a dynamic horizontal list.

  • It is a list where we can add or remove from the end.

• The Common Prefix Logic:

  • Add: Incremental change.
  • Remove & Add: Implies the prefix remains common. This allows us to maintain processing done on that prefix (like an "Undo" button in an editor).

• The Sorted (Monotonic) Stack:

  • Sometimes we need to keep the stack sorted.
  • When adding an element, if we pop elements to maintain order, whatever we pop is greater than our current element.
  • Logic: The current element is the "next smaller element" for everything we popped.

---

Tasks and Solutions

1. Valid Parentheses

• Tool: Stack and Greedy.
• Logic: Assume the object is valid. Push the first bracket. The moment we face its partner pair, pop it.

Click to expand solution code

bool isValid(string s) {
    vector<char> st;
    for (char c : s) {
        if (c == '(') st.push_back(c);
        else {
            if (st.empty() || st.back() != '(') return false;
            st.pop_back();
        }
    }
    return st.empty();
}

2. Maximum Nesting Depth

• Metric: The type of bracket doesn't matter; only the depth count matters.
• Logic: We push until max depth is reached. Therefore, maximum stack size = maximum nesting depth.

Click to expand solution code

int maxDepth(string s) {
    int d = 0, mx = 0;
    for (char c : s) {
        if (c == '(') mx = max(mx, ++d);
        else if (c == ')') d--;
    }
    return mx;
}

3. Minimum Add to Make Valid

• Tool: Prefix Sum.

• Logic:

  • Ensure prefix_sum >= 0 (closing brackets never exceed open ones).
  • If bal becomes -1 (invalid), we must add an open bracket (virtually).
  • At the end, add closing brackets equal to the remaining bal.

Click to expand solution code

int minAddToMakeValid(string s) {
    int bal = 0, ans = 0;
    for (char c : s) {
        bal += (c == '(' ? 1 : -1);
        if (bal == -1) { // Immediate violation check
            ans++; bal++;
        }
    }
    return ans + bal; // Add remaining open brackets
}

4. Minimum Remove to Make Valid

• Observation: This is the dual of "Minimum Add", but destructive.

• Logic:

  • Pass 1 (Left \(\to\) Right): Like Kadane’s Algo. If bal < 0, the current ) is useless. Remove it.
  • Pass 2 (Right \(\to\) Left): Remove any excess ( that were never closed.

Click to expand solution code

string minRemoveToMakeValid(string s) {
    string t = ""; int bal = 0;
    // Pass 1: Remove invalid ')'
    for (char c : s) {
        if (c == '(') { bal++; t += c; }
        else if (c == ')') { if (bal > 0) { bal--; t += c; } }
        else t += c;
    }
    string ans = ""; bal = 0;
    // Pass 2: Remove excess '('
    for (int i = t.size() - 1; i >= 0; i--) {
        if (t[i] == '(' && bal == 0) continue;
        if (t[i] == ')') bal++;
        else if (t[i] == '(') bal--;
        ans += t[i];
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

5. Validity with Mutable Places

• Scenario: Some positions are mutable (can be ( or )).

• Logic (Range Greedy):

  • Track a range [low, high] of possible open brackets.
  • low: Treat wildcards as ) (minimum possible open count).
  • high: Treat wildcards as ( (maximum possible open count).
  • If high < 0, it's impossible.
  • low must be clamped to 0 (physically can't have negative brackets).

Click to expand solution code

bool checkValidString(string s) { // s contains '(' , ')' or '*' (mutable)
    int lo = 0, hi = 0;
    for (char c : s) {
        lo += (c == '(' ? 1 : -1);
        hi += (c != ')' ? 1 : -1); // '*' counts as +1 for hi
        if (hi < 0) return false;
        lo = max(0, lo);
    }
    return lo == 0;
}

6. Split String for Maximum Depth

• Goal: Split string into two subsequences \(A\) and \(B\) to minimize the maximum depth.

• Logic:

  • We want to distribute the "height" evenly.
  • Assign Layer 1 to \(A\), Layer 2 to \(B\), Layer 3 to \(A\)...
  • This is just depth % 2.

Click to expand solution code

vector<int> maxDepthAfterSplit(string seq) {
    vector<int> ans(seq.size());
    int d = 0;
    for (int i = 0; i < seq.size(); ++i) {
        if (seq[i] == '(') ans[i] = d++ % 2;
        else ans[i] = --d % 2;
    }
    return ans;
}