Skip to content

Valid Parentheses Strings

Table of Contents

20. Valid Parentheses

  • LeetCode | LeetCode CH (Easy)

  • Tags: string, stack

  • Determine if the input string is valid.
  • Steps for the string ()[]{}:
char action stack
( push "("
) pop ""
[ push "["
] pop ""
{ push "{"
} pop ""
20. Valid Parentheses - Python Solution
# Stack
def isValid(s: str) -> bool:
    hashmap = {
        ")": "(",
        "]": "[",
        "}": "{",
    }
    stack = []

    for c in s:
        if c in hashmap:
            if stack and stack[-1] == hashmap[c]:
                stack.pop()
            else:
                return False
        else:
            stack.append(c)

    return True if not stack else False


print(isValid("()"))  # True
print(isValid("()[]{}"))  # True
print(isValid("(]"))  # False
20. Valid Parentheses - C++ Solution
#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

1963. Minimum Number of Swaps to Make the String Balanced - Python Solution
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

678. Valid Parenthesis String - Python Solution
# 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

2116. Check if a Parentheses String Can Be Valid - Python Solution
# 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
2116. Check if a Parentheses String Can Be Valid - C++ Solution
#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

32. Longest Valid Parentheses - Python Solution
# 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