2116. Check if a Parentheses String Can Be Valid

📝 Problem Details

• Title: 2116. Check if a Parentheses String Can Be Valid
• Link: https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/
• Difficulty: Medium
• Tags/Categories: Stack

💭What Were My Initial Thoughts?

- use a stack to keep track of open brackets
- iterate through the string
- check if the current char is an opening bracket
	- if it is, push it to the stack 
	- if it isnt, try and pop from the stack
		- if there is nothing in the stack, check if the bracket can be flipped (in locked array)
		- if it can, flip it to an open bracket and push it into the stack 
		- if not, return false

- return true or false if the stack is empty or not 

🤔What Did I Struggle With?

- Handling the flexibility of `locked == 0` and how to balance it effectively in the two-stack approach.
- Ensuring that indices in the stack are matched in order, especially during the second pass.
- Dealing with edge cases like odd-length strings or too many closing parentheses early in the string.

💡 Explanation of Solution

The solution uses a two-stack approach:

1. **Left-to-right pass:**
   - For every character:
     - If it is a locked `(`, push its index onto the `openStack`.
     - If it is an unlocked character (`locked[i] == 0`), push its index onto the `flexibleStack`.
     - If it is a locked `)`:
       - Match it with the top of `openStack` if possible.
       - Otherwise, match it with the top of `flexibleStack`.
       - If no match is possible, the string cannot be valid.

2. **Right-to-left pass:**
   - After the first pass, some unmatched `(` may remain in `openStack`.
   - Use indices from `flexibleStack` to balance the remaining `(`.
   - Ensure that the `(` occurs before the corresponding `0` in the order of the string.

3. Return true if all `(` are balanced; otherwise, return false.

⌛ Complexity Analysis

Time Complexity: O(n)
- Each character is processed once during the traversal

Space Complexity: O(n)
- Two stacks are used to store indices of `(` and `0`

💻 Implementation of Solution

class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n = s.size();
        if (n % 2 != 0) return false; // A valid string must have an even length.
 
        stack<int> openStack;    // To store indices of '(' with locked[i] == '1'
        stack<int> flexibleStack; // To store indices of unlocked characters (locked[i] == '0')
 
        // Left-to-right traversal
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(' && locked[i] == '1') {
                openStack.push(i); // Push locked '(' to openStack
            } else if (locked[i] == '0') {
                flexibleStack.push(i); // Push unlocked character to flexibleStack
            } else if (s[i] == ')') {
                // Match ')' with a locked '(' or an unlocked character
                if (!openStack.empty()) {
                    openStack.pop(); // Match with '('
                } else if (!flexibleStack.empty()) {
                    flexibleStack.pop(); // Match with unlocked character
                } else {
                    return false; // No match available
                }
            }
        }
 
        // Right-to-left traversal to match remaining '('
        while (!openStack.empty() && !flexibleStack.empty()) {
            if (openStack.top() < flexibleStack.top()) {
                openStack.pop();
                flexibleStack.pop();
            } else {
                return false; // Invalid if '(' appears after a flexible character
            }
        }
 
        // If any unmatched '(' remain, the string is invalid
        return openStack.empty();
    }
};