문제

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

input & output

Example 1

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Constraints

• 1 <= s.length <= 105
• s[i] is either'(' , ')', or lowercase English letter.

---

Approach #1

Solution #1

var minRemoveToMakeValid = function(s) {
    let res = [...s];
    let openIdx = [];
    
    for(let i=0; i<s.length; i++){
        if(s[i]==="(") openIdx.push(i);
        else if(s[i]===")") {
            if(openIdx.length > 0) openIdx.pop();
            else res[i] = "";
        }
    }
    
    while(openIdx.length > 0) res[openIdx.pop()] = "";
    
    return res.join("");
};

N: s.length

Time Complexity

O(N)

Space Complexity

O(N)

Review

테케는 통과했는데 내가 처음 생각한 로직으로는 완전 통과가 안되어서 솔루션 참고해 코드 정돈했다.
스택에 인덱스값을 넣어 해당 인덱스를 확인하며 string을 재구성 하는게 인상깊었음.

TIL

• string 쪼개서 배열에 넣을때 split 안쓰고 let arr = [...s] 로 해도 됨.

---

Approach #2

Solution #2

Time Complexity

Space Complexity

Review

TIL

---