# Valid Parentheses
**Difficulty:** EASY
[External](https://leetcode.com/problems/valid-parentheses)
Canonical: https://scaleengineer.com/dsa/problems/valid-parentheses
**Data structures:** String, Stack
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Accolite](https://scaleengineer.com/companies/accolite), [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Airbnb](https://scaleengineer.com/companies/airbnb), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Barclays](https://scaleengineer.com/companies/barclays), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Bolt](https://scaleengineer.com/companies/bolt), [Braze](https://scaleengineer.com/companies/braze), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [Criteo](https://scaleengineer.com/companies/criteo), [Deloitte](https://scaleengineer.com/companies/deloitte), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Epic Systems](https://scaleengineer.com/companies/epic-systems), [Expedia](https://scaleengineer.com/companies/expedia), [FreshWorks](https://scaleengineer.com/companies/freshworks), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Grab](https://scaleengineer.com/companies/grab), [HCL](https://scaleengineer.com/companies/hcl), [Huawei](https://scaleengineer.com/companies/huawei), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Mastercard](https://scaleengineer.com/companies/mastercard), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nagarro](https://scaleengineer.com/companies/nagarro), [Nvidia](https://scaleengineer.com/companies/nvidia), [Ozon](https://scaleengineer.com/companies/ozon), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Publicis Sapient](https://scaleengineer.com/companies/publicis-sapient), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Roblox](https://scaleengineer.com/companies/roblox), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Shopee](https://scaleengineer.com/companies/shopee), [Siemens](https://scaleengineer.com/companies/siemens), [Spotify](https://scaleengineer.com/companies/spotify), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [persistent systems](https://scaleengineer.com/companies/persistent-systems), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [Dell](https://scaleengineer.com/companies/dell), [Lucid Motors](https://scaleengineer.com/companies/lucid-motors), [Netflix](https://scaleengineer.com/companies/netflix), [Nike](https://scaleengineer.com/companies/nike), [SOTI](https://scaleengineer.com/companies/soti), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [ThoughtWorks](https://scaleengineer.com/companies/thoughtworks), [Turing](https://scaleengineer.com/companies/turing), [opentext](https://scaleengineer.com/companies/opentext), [Autodesk](https://scaleengineer.com/companies/autodesk), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Swiggy](https://scaleengineer.com/companies/swiggy), [Zenefits](https://scaleengineer.com/companies/zenefits), [BlackRock](https://scaleengineer.com/companies/blackrock), [Disney](https://scaleengineer.com/companies/disney), [Mitsogo](https://scaleengineer.com/companies/mitsogo), [X](https://scaleengineer.com/companies/x), [Booking.com](https://scaleengineer.com/companies/booking.com), [Anduril](https://scaleengineer.com/companies/anduril), [Bank of America](https://scaleengineer.com/companies/bank-of-america), [GE Healthcare](https://scaleengineer.com/companies/ge-healthcare), [Millennium](https://scaleengineer.com/companies/millennium), [Odoo](https://scaleengineer.com/companies/odoo), [Splunk](https://scaleengineer.com/companies/splunk), [Squarespace](https://scaleengineer.com/companies/squarespace), [Tencent](https://scaleengineer.com/companies/tencent), [Tripadvisor](https://scaleengineer.com/companies/tripadvisor), [UBS](https://scaleengineer.com/companies/ubs), [VK](https://scaleengineer.com/companies/vk), [Zillow](https://scaleengineer.com/companies/zillow)
---
## Problem
Given a string `s` containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

**Example 1:**

**Input:** s = "()"

**Output:** true

**Example 2:**

**Input:** s = "()\[\]{}"

**Output:** true

**Example 3:**

**Input:** s = "(\]"

**Output:** false

**Example 4:**

**Input:** s = "(\[\])"

**Output:** true

**Constraints:**

* `1 <= s.length <= 104`
* `s` consists of parentheses only `'()[]{}'`.

# Approaches
## Iterative Replacement
This approach repeatedly scans the string to find and remove valid adjacent pairs of parentheses, such as `()`, `[]`, or `{}`. If the string becomes empty after all possible pairs are removed, the original string is considered valid.
**Time:** O(N^2), where N is the length of the string. In the worst-case scenario (e.g., `((...))`), we might only remove one pair per iteration, and each `replace` operation can take O(N) time. This results in a quadratic time complexity. · **Space:** O(N), as string replacement operations in Java can create new string objects, potentially requiring space proportional to the original string's length.
**Pros:** Simple to understand and implement without explicit data structures like a stack.
**Cons:** Inefficient for long strings due to repeated string traversals and replacements.; Can be significantly slower than the stack-based approach.
### Explanation
The core idea is to simplify the string iteratively. We repeatedly look for and eliminate the innermost valid pairs of parentheses. If we can eliminate all characters in the string this way, it means every bracket was properly matched and nested.

- Start with the input string `s`.
- Enter a loop that continues as long as we can find and remove a valid pair.
- Inside the loop, use string replacement functions to remove all occurrences of `"()"`, `"[]"`, and `"{}"`.
- If the string's length does not change after an iteration, it means no more valid pairs can be removed, so we break the loop.
- After the loop terminates, check if the resulting string is empty.
- If it's empty, all parentheses were matched and removed correctly, so the original string is valid.
- If it's not empty, it contains mismatched or extra parentheses, making the original string invalid.

```java
class Solution {
    public boolean isValid(String s) {
        int lengthBefore;
        do {
            lengthBefore = s.length();
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        } while (lengthBefore != s.length());
        
        return s.isEmpty();
    }
}
```
### Algorithm
- Initialize a loop that runs as long as the length of the string `s` is being reduced.
- In each iteration, store the length of `s` before modification.
- Replace all occurrences of `"()"`, `"[]"`, and `"{}"` with an empty string.
- If the length of `s` remains unchanged after the replacements, break the loop.
- After the loop, if `s` is empty, return `true`.
- Otherwise, return `false`.

## Stack-Based Approach
This is the classic and most efficient approach for this problem. It utilizes a stack to keep track of open brackets. The Last-In, First-Out (LIFO) nature of a stack is perfect for matching the most recently opened bracket with its corresponding closing bracket.
**Time:** O(N), where N is the length of the string. We perform a single pass through the string, and each stack operation (push, pop, peek) takes constant time, O(1). · **Space:** O(N) in the worst case. If the string consists of only opening brackets (e.g., `((((...))))`), the stack will grow to the size of the input string.
**Pros:** Highly efficient with linear time complexity.; The standard and optimal solution for this type of matching problem.
**Cons:** Requires understanding and use of a stack data structure.; Uses extra space for the stack.
### Explanation
This approach leverages a stack to enforce the LIFO (Last-In, First-Out) order of parenthesis matching. When we encounter an opening bracket, we 'save' it for later. When we see a closing bracket, we check if it matches the last saved opening bracket.

- Initialize an empty stack (e.g., `java.util.Stack` or `java.util.ArrayDeque`).
- Iterate through each character `c` of the input string.
- If `c` is an opening bracket (`(`, `{`, `[`), push it onto the stack. This signifies that we need to find its corresponding closing bracket later.
- If `c` is a closing bracket (`)`, `}`, `]`):
  - First, check if the stack is empty. If it is, we have a closing bracket with no preceding open bracket, so the string is invalid. Return `false`.
  - If the stack is not empty, pop the top element. This element should be the most recently seen opening bracket.
  - Check if the popped element is the correct opening bracket for the current closing bracket `c`. For example, if `c` is `)`, the popped element must be `(`. If they don't match, the order is incorrect. Return `false`.
- After the loop finishes, if the stack is empty, it means every opening bracket had a corresponding closing bracket in the correct order. Return `true`.
- If the stack is not empty, it means there are unclosed opening brackets left over. Return `false`.

```java
import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
```
### Algorithm
- Initialize an empty stack of characters.
- Iterate through each character `c` in the input string `s`.
- If `c` is an opening bracket (`(`, `{`, or `[`), push it onto the stack.
- If `c` is a closing bracket (`)`, `}`, or `]`):
  - If the stack is empty, it means there is a closing bracket without a corresponding opening one. Return `false`.
  - Pop the top character from the stack.
  - If the popped character is not the matching opening bracket for `c`, return `false`.
- After the loop, if the stack is empty, all brackets have been matched. Return `true`.
- If the stack is not empty, it means there are unmatched opening brackets. Return `false`.

# Solutions
### CSharp

```csharp
public class Solution {
    public bool IsValid(string s) {
        Stack < char > stk = new Stack < char > ();
        foreach(var c in s.ToCharArray()) {
            if (c == '(') {
                stk.Push(')');
            } else if (c == '[') {
                stk.Push(']');
            } else if (c == '{') {
                stk.Push('}');
            } else if (stk.Count == 0 || stk.Pop() != c) {
                return false;
            }
        }
        return stk.Count == 0;
    }
}
```

### Java

```java
class Solution { public boolean isValid ( String s ) { Deque < Character > stk = new ArrayDeque <>(); for ( char c : s . toCharArray ()) { if ( c == '(' || c == '{' || c == '[' ) { stk . push ( c ); } else if ( stk . isEmpty () || ! match ( stk . pop (), c )) { return false ; } } return stk . isEmpty (); } private boolean match ( char l , char r ) { return ( l == '(' && r == ')' ) || ( l == '{' && r == '}' ) || ( l == '[' && r == ']' ); } }
```

### JavaScript

```javascript
/** * @param {string} s * @return {boolean} */ var isValid = function (s) {
  let stk = [];
  for (const c of s) {
    if (c == " ( " || c == " { " || c == " [ ") {
      stk.push(c);
    } else if (stk.length == 0 || !match(stk[stk.length - 1], c)) {
      return false;
    } else {
      stk.pop();
    }
  }
  return stk.length == 0;
};
function match(l, r) {
  return (
    (l == " ( " && r == " ) ") ||
    (l == " [ " && r == " ] ") ||
    (l == " { " && r == " } ")
  );
}

```

### CPP

```cpp
class Solution {
public:
  bool isValid(string s) {
    string stk;
    for (char c : s) {
      if (c == '(' || c == '{' || c == '[')
        stk.push_back(c);
      else if (stk.empty() || !match(stk.back(), c))
        return false;
      else
        stk.pop_back();
    }
    return stk.empty();
  }
  bool match(char l, char r) {
    return (l == '(' && r == ')') || (l == '[' && r == ']') ||
           (l == '{' && r == '}');
  }
};

```

### Python

```python
class Solution : def isValid ( self , s : str ) -> bool : stk = [] d = { '()' , '[]' , '{}' } for c in s : if c in '({[' : stk . append ( c ) elif not stk or stk . pop () + c not in d : return False return not stk
```