Skip to content

Valid Parentheses Strings

Table of Contents

20. Valid Parentheses

# Stack
def is_valid(s: str) -> bool:
    if len(s) % 2:
        return False

    pairs = {
        "(": ")",
        "{": "}",
        "[": "]",
    }
    stack = []
    for ch in s:
        if ch in pairs:
            stack.append(ch)
        elif not stack or ch != pairs[stack.pop()]:
            return False

    return True if not stack else False


def test_is_valid():
    assert is_valid("()[]{}")
    assert not is_valid("(]")
    assert not is_valid("([)]")
    assert is_valid("{[]}")

#include <cassert>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
   public:
    bool isValid(string s) {
        unordered_map<char, char> map{{')', '('}, {'}', '{'}, {']', '['}};
        stack<char> stack;
        if (s.length() % 2 == 1) return false;

        for (char& ch : s) {
            if (stack.empty() || map.find(ch) == map.end()) {
                stack.push(ch);
            } else {
                if (map[ch] != stack.top()) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.empty();
    }
};

int main() {
    Solution s;
    assert(s.isValid("()") == true);
    assert(s.isValid("()[]{}") == true);
    assert(s.isValid("(]") == false);
    assert(s.isValid("([)]") == false);
    assert(s.isValid("{[]}") == true);
    return 0;
}

921. Minimum Add to Make Parentheses Valid

1021. Remove Outermost Parentheses

1614. Maximum Nesting Depth of the Parentheses

1190. Reverse Substrings Between Each Pair of Parentheses

856. Score of Parentheses

1249. Minimum Remove to Make Valid Parentheses

1963. Minimum Number of Swaps to Make the String Balanced

def minSwaps(s: str) -> int:
    res, balance = 0, 0

    for char in s:
        if char == "[":
            balance += 1
        elif balance > 0:
            balance -= 1
        else:
            res += 1
            balance += 1

    return res


if __name__ == "__main__":
    print(minSwaps("][]["))  # 1
    print(minSwaps("]]][[["))  # 2

678. Valid Parenthesis String

# Greedy
def checkValidString(s: str) -> bool:
    min_open, max_open = 0, 0

    for char in s:
        if char == "(":
            min_open += 1
            max_open += 1
        elif char == ")":
            min_open = max(min_open - 1, 0)
            max_open -= 1
        elif char == "*":
            min_open = max(min_open - 1, 0)
            max_open += 1

        if max_open < 0:
            return False

    return min_open == 0


s = "(*))"
print(checkValidString(s))  # True

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

1541. Minimum Insertions to Balance a Parentheses String

2116. Check if a Parentheses String Can Be Valid

# Valid Parentheses Strings
def canBeValid(s: str, locked: str) -> bool:
    if len(s) % 2:
        return False

    mx, mn = 0, 0
    for ch, lock in zip(s, locked):
        if lock == "1":
            d = 1 if ch == "(" else -1
            mx += d
            if mx < 0:
                return False
            mn += d
        else:
            mx += 1
            mn -= 1

        if mn < 0:
            mn = 1

    return mn == 0


if __name__ == "__main__":
    s = "))()))"
    locked = "010100"
    print(canBeValid(s, locked))  # True

#include <iostream>
#include <string>
using namespace std;

// Valid Parentheses Strings
bool canBeValid(string s, string locked) {
    if (s.length() % 2 != 0) {
        return false;
    }

    int mx = 0, mn = 0;
    for (size_t i = 0; i < s.length(); ++i) {
        char ch = s[i];
        char lock = locked[i];

        if (lock == '1') {
            int d = (ch == '(') ? 1 : -1;
            mx += d;
            if (mx < 0) {
                return false;
            }
            mn += d;
        } else {
            mx += 1;
            mn -= 1;
        }

        if (mn < 0) {
            mn = 1;
        }
    }

    return mn == 0;
}

int main() {
    string s = "))()))";
    string locked = "010100";
    cout << (canBeValid(s, locked) ? "true" : "false") << endl;  // true
    return 0;
}

32. Longest Valid Parentheses

# Stack
def longestValidParentheses(s: str) -> int:
    stack = [-1]
    res = 0

    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        elif ch == ")":
            stack.pop()
            if stack:
                res = max(res, i - stack[-1])
            else:
                stack.append(i)

    return res


if __name__ == "__main__":
    print(longestValidParentheses("(()"))  # 2
    print(longestValidParentheses(")()())"))  # 4

Comments