Check if a Parentheses String Can Be Valid

Medium
1413.

Check if a Parentheses String Can Be Valid

Check if a Parentheses String Can Be Valid is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Meta interviews.

A parentheses string is valid if it is empty, or is AB for valid strings A and B, or is (A) for a valid string A — in other words every ( is closed by a later matching ).

You are given a string s of ( and ) and a binary string locked of the same length. If locked[i] is '1', the character s[i] is fixed. If locked[i] is '0', you may change s[i] to either ( or ).

Return true if you can make s valid.

Example 1

Input
s = "))((", locked = "0110"
Output
true
Explanation
Change the first character to `(` and the last to `)`: `()()`.

Example 2

Input
s = "(((", locked = "000"
Output
false
Explanation
An odd-length string can never be valid.

Example 3

Input
s = "())(", locked = "1101"
Output
false
Explanation
The last character is a locked `(` that nothing after it can close.

Constraints

  • n == s.length == locked.length
  • 1 <= n <= 10^5
  • s[i] is '(' or ')'
  • locked[i] is '0' or '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} locked
 * @return {boolean}
 */
var canBeValid = function(s, locked) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check if a Parentheses String Can Be Valid — Solution

Check if a Parentheses String Can Be Valid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check if a Parentheses String Can Be Valid is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy, Stack
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A parentheses string is valid if it is empty, or is AB for valid strings A and B, or is (A) for a valid string A — in other words every ( is closed by a later matching ).

You are given a string s of ( and ) and a binary string locked of the same length. If locked[i] is '1', the character s[i] is fixed. If locked[i] is '0', you may change s[i] to either ( or ).

Return true if you can make s valid.

Example 1

Input: s = "))((", locked = "0110"
Output: true
Explanation: Change the first character to `(` and the last to `)`: `()()`.

Example 2

Input: s = "(((", locked = "000"
Output: false
Explanation: An odd-length string can never be valid.

Example 3

Input: s = "())(", locked = "1101"
Output: false
Explanation: The last character is a locked `(` that nothing after it can close.

Constraints

  • n == s.length == locked.length
  • 1 <= n <= 10^5
  • s[i] is '(' or ')'
  • locked[i] is '0' or '1'

Hints for Check if a Parentheses String Can Be Valid

  1. Hint 1

    An odd length is hopeless. Otherwise, think of every unlocked position as a wildcard.

  2. Hint 2

    Reading left to right, each locked ) needs some earlier ( or wildcard to match it. Reading right to left, each locked ( needs a later ) or wildcard.

  3. Hint 3

    Two counters suffice: left to right, count ( or wildcard as +1 and locked ) as -1 and fail if it goes negative; then the mirror pass from the right.

How to solve Check if a Parentheses String Can Be Valid

Treat unlocked characters as wildcards. A string with wildcards can be completed exactly when its length is even, no prefix has more locked ) than other characters, and no suffix has more locked ( than other characters.

Approach

  1. If n is odd, return false.
  2. Left to right: bal += 1 for a wildcard or a locked (, bal -= 1 for a locked ); if bal < 0, return false.
  3. Right to left: bal += 1 for a wildcard or a locked ), bal -= 1 for a locked (; if bal < 0, return false.
  4. Return true.

Why it works

Both conditions are clearly necessary: a locked ) needs a partner on its left and a locked ( a partner on its right. They are also sufficient: the forward pass guarantees enough openers for every locked closer, the backward pass enough closers for every locked opener, and with an even length the leftover wildcards can be split into matching halves — the first half of them opened, the second half closed — which keeps every prefix balance non-negative and ends at zero.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • One pass is not enough: "()((" with only the last two characters locked passes the forward check and fails the backward one.
  • Forgetting the odd-length check gives true for an all-wildcard string such as "(((" with locked = "000".
  • Treat a wildcard as helping both passes — it is +1 in each direction.

Reference solution

Python

def canBeValid(s: str, locked: str) -> bool:
    n = len(s)
    if n % 2 == 1:
        return False
    bal = 0
    for i in range(n):
        bal += 1 if locked[i] == '0' or s[i] == '(' else -1
        if bal < 0:
            return False
    bal = 0
    for i in range(n - 1, -1, -1):
        bal += 1 if locked[i] == '0' or s[i] == ')' else -1
        if bal < 0:
            return False
    return True

Java

public static boolean canBeValid(String s, String locked) {
    int n = s.length();
    if (n % 2 == 1) return false;
    int bal = 0;
    for (int i = 0; i < n; i++) {
        bal += (locked.charAt(i) == '0' || s.charAt(i) == '(') ? 1 : -1;
        if (bal < 0) return false;
    }
    bal = 0;
    for (int i = n - 1; i >= 0; i--) {
        bal += (locked.charAt(i) == '0' || s.charAt(i) == ')') ? 1 : -1;
        if (bal < 0) return false;
    }
    return true;
}

C++

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

JavaScript

var canBeValid = function(s, locked) {
    var n = s.length;
    if (n % 2 === 1) return false;
    var bal = 0;
    for (var i = 0; i < n; i++) {
        bal += (locked[i] === "0" || s[i] === "(") ? 1 : -1;
        if (bal < 0) return false;
    }
    bal = 0;
    for (var j = n - 1; j >= 0; j--) {
        bal += (locked[j] === "0" || s[j] === ")") ? 1 : -1;
        if (bal < 0) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms