Check if a Parentheses String Can Be Valid

Check if a Parentheses String Can Be Valid - Problem

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

It is ().
It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
It can be written as (A), where A is a valid parentheses string.

You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked:

If locked[i] is '1', you cannot change s[i].
If locked[i] is '0', you can change s[i] to either '(' or ')'.

Return true if you can make s a valid parentheses string. Otherwise, return false.

Input & Output

Example 1 — Simple Valid Case

$ Input: s = "))", locked = "00"

› Output: true

💡 Note: Both positions are unlocked. We can change them to "()" to make a valid parentheses string.

Example 2 — Impossible Case

$ Input: s = "())", locked = "000"

› Output: false

💡 Note: String has odd length (3), so it's impossible to create a valid parentheses string.

Example 3 — Mixed Locked/Unlocked

$ Input: s = "((((", locked = "1010"

› Output: true

💡 Note: Positions 0,2 are locked as '('. Positions 1,3 are unlocked, we can set them to ')' to get "()()".

Constraints

n == s.length == locked.length
1 ≤ n ≤ 10⁵
s[i] is either '(' or ')'
locked[i] is either '0' or '1'

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String with locked/unlocked positions marked

Greedy Assignment

Assign unlocked positions optimally

Validation

Check if result forms valid parentheses

Key Takeaway

🎯 Key Insight: Greedy assignment ensures we maintain proper balance while respecting locked constraints

Asked in

G Google 15 M Microsoft 12 a Amazon 8 f Meta 6

The key insight is that we need exactly n/2 opening and n/2 closing brackets, and we can greedily assign unlocked positions. The greedy approach works optimally by ensuring we never run out of opening brackets when we need them. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Simulation	O(n)	O(n)	Use stack to track balance while making greedy choices for unlocked positions
Brute Force - Try All Combinations	O(2^k × n)	O(k)	Generate all possible combinations of unlocked positions and check validity
Greedy Two-Pass Strategy	O(n)	O(1)	Make greedy choices in two passes to balance parentheses optimally

Stack-Based Simulation — Algorithm Steps

Traverse string left to right
For locked positions: push '(' or pop for ')'
For unlocked positions: choose '(' if stack is empty or choose ')' if we have excess opens
Check if stack is empty at the end and we used equal opens/closes

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Chars

Handle locked positions and make greedy choices for unlocked

Stack Operations

Push '(' or pop for ')' based on current state

Final Check

Verify stack is empty and counts are balanced

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* s, char* locked) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    
    char* stack = malloc(n * sizeof(char));
    int stackSize = 0;
    int opensUsed = 0;
    int closesUsed = 0;
    int unlockedCount = 0;
    
    for (int i = 0; i < n; i++) {
        if (locked[i] == '0') unlockedCount++;
    }
    
    for (int i = 0; i < n; i++) {
        if (locked[i] == '1') {
            // Position is locked
            if (s[i] == '(') {
                stack[stackSize++] = '(';
                opensUsed++;
            } else {  // s[i] == ')'
                if (stackSize > 0) {
                    stackSize--;
                    closesUsed++;
                } else {
                    free(stack);
                    return false;  // No matching opening bracket
                }
            }
        } else {
            // Position is unlocked, make greedy choice
            int remainingChars = n - i - 1;
            int opensNeeded = n / 2 - opensUsed;
            
            if (opensNeeded > remainingChars - (unlockedCount - 1)) {
                // Must use '(' here
                stack[stackSize++] = '(';
                opensUsed++;
            } else if (stackSize > 0) {
                // Can use ')' to close existing opening
                stackSize--;
                closesUsed++;
            } else {
                // Must use '(' since stack is empty
                stack[stackSize++] = '(';
                opensUsed++;
            }
            
            unlockedCount--;
        }
    }
    
    bool result = stackSize == 0 && opensUsed == n / 2;
    free(stack);
    return result;
}

int main() {
    char s[100001], locked[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    fgets(locked, sizeof(locked), stdin);
    locked[strcspn(locked, "\n")] = 0;
    
    bool result = solution(s, locked);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string with constant time stack operations

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n/2 opening brackets in worst case

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler