Check if a Parentheses String Can Be Valid

medium stack greedy parentheses

Problem

You are given a parentheses string s and a binary string locked of the same length. Wherever locked[i] is '1' the character s[i] is frozen in place; wherever it is '0' you may flip s[i] to either '(' or ')'.

Decide whether some choice for the free positions turns s into a valid parentheses string — one where every prefix has at least as many '(' as ')' and the totals match.

Inputs = "))()))", locked = "010100"

Outputtrue

Positions 1 and 3 hold locked ')', but flipping the free s[0] and s[4] to '(' gives "()()()".

s (only ( and ) characters)

locked (0 = free to flip, 1 = fixed)

def can_be_valid(s, locked):
    if len(s) % 2 == 1:
        return False
    bal = 0                       # forward: too many locked ')'?
    for i in range(len(s)):
        if locked[i] == '0' or s[i] == '(':
            bal += 1
        else:
            bal -= 1
        if bal < 0:
            return False
    bal = 0                       # backward: too many locked '('?
    for i in range(len(s) - 1, -1, -1):
        if locked[i] == '0' or s[i] == ')':
            bal += 1
        else:
            bal -= 1
        if bal < 0:
            return False
    return True

function canBeValid(s, locked) {
  if (s.length % 2 === 1) return false;
  let bal = 0;                    // forward: too many locked ')'?
  for (let i = 0; i < s.length; i++) {
    if (locked[i] === '0' || s[i] === '(') bal++;
    else bal--;
    if (bal < 0) return false;
  }
  bal = 0;                        // backward: too many locked '('?
  for (let i = s.length - 1; i >= 0; i--) {
    if (locked[i] === '0' || s[i] === ')') bal++;
    else bal--;
    if (bal < 0) return false;
  }
  return true;
}

boolean canBeValid(String s, String locked) {
    if (s.length() % 2 == 1) return false;
    int bal = 0;                  // forward: too many locked ')'?
    for (int i = 0; i < s.length(); i++) {
        if (locked.charAt(i) == '0' || s.charAt(i) == '(') bal++;
        else bal--;
        if (bal < 0) return false;
    }
    bal = 0;                      // backward: too many locked '('?
    for (int i = s.length() - 1; i >= 0; i--) {
        if (locked.charAt(i) == '0' || s.charAt(i) == ')') bal++;
        else bal--;
        if (bal < 0) return false;
    }
    return true;
}

bool canBeValid(string s, string locked) {
    if (s.size() % 2 == 1) return false;
    int bal = 0;                  // forward: too many locked ')'?
    for (int i = 0; i < (int)s.size(); i++) {
        if (locked[i] == '0' || s[i] == '(') bal++;
        else bal--;
        if (bal < 0) return false;
    }
    bal = 0;                      // backward: too many locked '('?
    for (int i = (int)s.size() - 1; i >= 0; i--) {
        if (locked[i] == '0' || s[i] == ')') bal++;
        else bal--;
        if (bal < 0) return false;
    }
    return true;
}

Explanation

Every unlocked position is a wildcard: it can lean open or closed, whichever helps. So instead of trying assignments, we only need to check that no stretch of the string is forced into failure by its locked characters. A stack of indices could pair things off explicitly, but a greedy balance counter captures exactly the same information.

Forward pass: scan left to right and keep an optimistic open-bracket balance — count +1 for every locked '(' and every free slot (it could be an open), and −1 only for a locked ')'. If this balance ever dips below zero, some prefix contains more immovable ')' than all the characters before them could possibly match, and no assignment can fix it.

Backward pass: the mirror check. Scan right to left counting +1 for locked ')' and free slots, −1 for locked '('. Going negative here means some suffix has a surplus of immovable '(' with nothing to their right to close them.

Together with the even-length requirement, the two bounds are sufficient: the forward pass shows the achievable balance can stay at or above zero at every prefix, the backward pass shows it can also finish at zero, and since each free slot shifts the balance by exactly ±2 when flipped, every value between those extremes of matching parity is reachable. A concrete valid assignment therefore exists.

For s = "))()))", locked = "010100": forward gives balances 1, 0, 1, 0, 1, 2 — never negative, because the free slots at 0, 2, 4, 5 soak up the locked ')' at 1 and 3. Backward gives 1, 2, 3, 4, 5, 6 — also clean, since there is no locked '(' at all. Both passes succeed, so the answer is true (e.g. "()()()").

Each pass is a single linear scan with one integer of bookkeeping, so the whole check runs in O(n) time and O(1) extra space — no stack ever needs to be materialised.

Time: O(n) Space: O(1)