LeetCode - 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.

입출력 예시

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"

제약사항

1 <= s.length <= 10^5
s[i] is one of  '(' , ')' and lowercase English letters.

Solution

[전략]

• 문자열의 문자 하나하나를 순회하며 StringBuilder에 append한다
• 여는 괄호는 짝이 안맞는 경우 삭제를 위해 index를 스택에 기록해놓는다. 여기서의 index는 기존 String의 index가 아니고 StringBuilder에 포함되며 할당된 index이다.
• 닫는 괄호의 경우 앞에 짝이 맞는 여는 괄호가 없으면 반드시 삭제해야하므로 StringBuilder에 포함시키지 않는다.
  => 짝이 맞지 않는 닫는 괄호를 무시하고 continue하게 되므로 기존 String과 StringBuilder의 index가 차이나게 된다.
• 닫는 괄호의 경우 앞에 짝이 맞는 여는 괄호가 있으면, 해당 여는 괄호는 삭제할 필요가 없기 때문에 stack에서 pop한다.
• stack에 남은 index의 여는 괄호는 삭제한다.

import java.util.*;

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> openBracketIdxs = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int sbIdx = 0;

        for(char ch : s.toCharArray()){
            if (ch == '(') {
                openBracketIdxs.push(sbIdx);
            } else if (ch == ')') {
                if (openBracketIdxs.isEmpty()) {
                    // 앞에 '(' 이 없어서 짝이 안맞는 ')'는 삭제해야하므로 sb에 append하지않고 sbIdx를 증가시키지도 않음
                    continue;
                } else {
                    openBracketIdxs.pop();
                }
            }
            sb.append(ch);
            sbIdx++;
        }
        while (!openBracketIdxs.isEmpty()) {
            int deleteIdx = openBracketIdxs.pop();
            sb.deleteCharAt(deleteIdx);
        }

        return sb.toString();
    }
    
}