Practice Projects

Check if a Parentheses String Can Be Valid

Problem Statement

Ek parentheses string ek non-empty string hoti hai jo sirf ‘(‘ aur ‘)’ se bani hoti hai. Yeh valid tab hoti hai jab yeh conditions true ho:

  1. Yeh () ho.

  2. Isko AB (A aur B ka concatenation) ke roop mein likha ja sakta ho, jahan A aur B valid parentheses strings hain.

  3. Isko (A) ke roop mein likha ja sakta ho, jahan A ek valid parentheses string hai.

Tumhe ek parentheses string s aur ek string locked di gayi hai, dono ki length n hai. locked ek binary string hai jisme sirf ‘0’s aur ‘1’s hain. Har index i ke liye:

  1. Agar locked[i] ‘1’ hai, toh tum s[i] ko change nahi kar sakte.

  2. Agar locked[i] ‘0’ hai, toh tum s[i] ko ‘(‘ ya ‘)’ mein badal sakte ho.

Return karo true agar tum s ko ek valid parentheses string bana sakte ho. Warna, return karo false.

Examples:

Example 1:

  • Input: s = "))()))", locked = "010100"

  • Output: true

  • Explanation: locked[1] == '1' aur locked[3] == '1', isliye hum s[1] ya s[3] ko change nahi kar sakte. Hum s[0] aur s[4] ko ‘(‘ mein badal dete hain aur s[2] aur s[5] ko unchanged chhod dete hain, aur s valid ban jati hai.

Example 2:

  • Input: s = "()()", locked = "0000"

  • Output: true

  • Explanation: Humein koi changes karne ki zarurat nahi kyunki s pehle se hi valid hai.

Example 3:

  • Input: s = ")", locked = "0"

  • Output: false

  • Explanation: locked humein s[0] ko change karne ki izin deti hai. s[0] ko ‘(‘ yaar ‘)’ mein badalne se s valid nahi banegi.

Constraints:

  • n == s.length == locked.length

  • 1 <= n <= 105

  • s[i] ( ya)

  • locked[i] ‘0 ya1`’

Practice Projects

Check if a Parentheses String Can Be Valid

Balanced Parentheses Check: Pehli baat yeh ensure karni hai ke parentheses string mein balanced parentheses honi chahiye. Balanced parentheses ka matlab hai ke har opening parenthesis '(' ka ek corresponding closing parenthesis ')' hona chahiye.

Two-Pass Check: Yeh approach do passes mein check karegi, left se right aur right se left.
First Pass (left se right):
Ek counter maintain karo jo track karega opening aur closing parentheses ka balance.
Jab bhi tum ( dekhoge, counter ko increment karo.
Jab bhi tum ) dekhoge, counter ko decrement karo.
Agar kisi bhi point par counter negative ho jaye, toh yeh indicate karega ke closing parentheses zyada hain aur hum isko valid nahi bana sakte without changes.
Second Pass (right se left):
Fir se ek counter maintain karo, lekin iss baar string ko right se left traverse karo.
Jab bhi tum ) dekhoge, counter ko increment karo.
Jab bhi tum ( dekhoge, counter ko decrement karo.
Agar kisi bhi point par counter negative ho jaye, toh yeh indicate karega ke opening parentheses zyada hain aur hum isko valid nahi bana sakte without changes.
Make Use of Locked String:
Jab tum locked[i] == '1' dekhoge, tab tum wo parentheses change nahi kar sakte.
Jab tum locked[i] == '0' dekhoge, tab tum wo parentheses change kar sakte ho agar zarurat pade.

Approach
Time Complexity:

  • First Pass (left se right):

    • Yeh pass string s ko ek baar traverse karta hai, jo O(n) time leta hai jahan n string ki length hai.

  • Second Pass (right se left):

    • Yeh pass bhi string s ko ek baar traverse karta hai, jo O(n) time leta hai.

Isliye overall time complexity O(n) hoti hai kyunki hum string ko sirf do baar traverse karte hain.

Space Complexity:

  • Additional Space:

    • Yeh approach constant auxiliary space use karti hai, mainly ek balance counter.

Isliye overall space complexity O(1) hoti hai kyunki hum koi extra space proportional to input size (n) use nahi kar rahe hain.

Solution

				
					var canBeValid = function(s, locked) {
    // Agar s ki length odd hai, toh valid nahi ho sakti
    if (s.length % 2 !== 0) return false;

    // Pehla pass: left se right check karte hain
    let balance = 0;
    for (let i = 0; i < s.length; i++) {
        // Agar locked[i] '0' hai ya s[i] '(', toh balance increment karo
        if (locked[i] === '0' || s[i] === '(') {
            balance++;
        } else if (s[i] === ')') { // Agar s[i] ')', toh balance decrement karo
            balance--;
        }
        // Agar kabhi bhi balance negative ho jaye, return false
        if (balance < 0) return false;
    }

    // Dusra pass: right se left check karte hain
    balance = 0;
    for (let i = s.length - 1; i >= 0; i--) {
        // Agar locked[i] '0' hai ya s[i] ')', toh balance increment karo
        if (locked[i] === '0' || s[i] === ')') {
            balance++;
        } else if (s[i] === '(') { // Agar s[i] '(', toh balance decrement karo
            balance--;
        }
        // Agar kabhi bhi balance negative ho jaye, return false
        if (balance < 0) return false;
    }

    // Agar dono passes mein balance non-negative raha, return true
    return true;
};

  • Pehla step function yeh dekhne ke liye check karta hai ki agar string s ki length odd number hai toh return false kar do. Ye isliye because ek valid parentheses string hamesha even length ki hoti hai.

    First Pass (left se right):

    Ek balance variable maintain kiya jata hai, jo opening aur closing parentheses ko track karta hai. Phir string ko left se right iterate karte hain:

    • Agar locked string ka current character '0' hai ya current character '(' hai toh balance increment hota hai.

    • Agar current character ')' hai, toh balance decrement hota hai.

    • Agar balance kabhi bhi negative hota hai, matlab close parentheses zyada hai bina opening parentheses ke, toh return false kar do.

    Second Pass (right se left):

    Fir se ek balance variable maintain hota hai, lekin is baar string ko right se left iterate karte hain:

    • Agar locked string ka current character '0' hai ya current character ')' hai toh balance increment hota hai.

    • Agar current character '(' hai, toh balance decrement hota hai.

    • Agar balance kabhi bhi negative hota hai, matlab opening parentheses zyada hai bina closing parentheses ke, toh return false kar do.

Solution

				
					class Solution {
public:
    bool canBeValid(string str, string lockStatus) {
        // Agar string ki length odd number hai, toh return false
        if (str.size() % 2 != 0) 
            return false;

        // Pehla pass: left se right traverse karta hai
        int openCount = 0;
        for (int i = 0; i < str.size(); ++i) {
            // Agar lockStatus[i] '0' hai ya str[i] '(', toh openCount increment karo
            if (lockStatus[i] == '0' || str[i] == '(') 
                openCount++;
            else 
                openCount--; // Agar str[i] ')', toh openCount decrement karo
            // Agar kabhi bhi openCount negative ho jaye, return false
            if (openCount < 0) 
                return false;
        }

        // Dusra pass: right se left traverse karta hai
        openCount = 0;
        for (int i = str.size() - 1; i >= 0; --i) {
            // Agar lockStatus[i] '0' hai ya str[i] ')', toh openCount increment karo
            if (lockStatus[i] == '0' || str[i] == ')') 
                openCount++;
            else 
                openCount--; // Agar str[i] '(', toh openCount decrement karo
            // Agar kabhi bhi openCount negative ho jaye, return false
            if (openCount < 0) 
                return false;
        }

        // Agar dono passes mein openCount non-negative raha, return true
        return true;
    }
};

Pehle function check karta hai agar string str ki length odd hai, toh directly false return kar do kyunki valid parentheses string hamisha even length ki hoti hai.

Pehla Pass (left se right traversal):

Ek counter maintain kiya jata hai, jo opening aur closing parentheses ka balance track karta hai. String ko left se right iterate karte hain:

  • Agar lockStatus string ka current character '0' hai ya current character '(' hai, toh counter increment hota hai.

  • Agar current character ')' hai, toh counter decrement hota hai.

  • Agar kabhi bhi counter negative ho jata hai, iska matlab closing parentheses zyada hain bina matching opening parentheses ke, toh false return kar do.

Dusra Pass (right se left traversal):

Fir se ek counter maintain kiya jata hai, lekin is baar string ko right se left iterate karte hain:

  • Agar lockStatus string ka current character '0' hai ya current character ')' hai, toh counter increment hota hai.

  • Agar current character '(' hai, toh counter decrement hota hai.

  • Agar kabhi bhi counter negative ho jata hai, iska matlab opening parentheses zyada hain bina closing parentheses ke, toh false return kar do.