[leetcode #1249] Minimum Remove to Make Valid Parentheses

Problem

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"

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.

Idea

주어진 문자열에서 유효하지 않은 괄호들을 최소한의 개수로 제거하고 유효한 문자열을 반환하는 문제다.

유효하지 않은 괄호가 나왔을 때 처리를 어떻게 하느냐에 따라 문제를 푸는 방식이 달라진다. 나는 list에 '('가 등장했을 때 index를 저장하고, gndp ')'가 등장하면 '('를 list에서 제거하는 방식으로 풀었다. 만약 ')'가 등장했는데 list가 비어있다면 유효하지 않은 괄호이므로 ')'를 문자열에 넣지 않는다. 이 때 deletedCnt를 하나씩 올려 추후에 유효하지 않은 '('를 제거할 때 사용한다.

문자열 전체를 탐색했음에도 '('가 list에 남아있다면 유효하지 않은 괄호다. 해당 문자의 index를 list에 담아뒀으므로 문자열에서 제거해준 뒤 반환하면 된다.

Time Complexity: O(n)
Space Complexity: O(n)

Solution

class Solution {
    public String minRemoveToMakeValid(String s) {
        List<Integer> openBraces = new ArrayList<>();
        StringBuilder strBuilder = new StringBuilder();
        int deletedCnt = 0;

        for (int i=0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                openBraces.add(i);
            } else if (s.charAt(i) == ')') {
                if (openBraces.size() == 0) {
                    deletedCnt++;
                    continue;
                } else {
                    openBraces.remove(openBraces.size()-1);
                }
            }

            strBuilder.append(s.charAt(i));
        }

        int cnt = 0;
        for (int i : openBraces) {
            strBuilder.delete(i - deletedCnt - cnt, i - deletedCnt - cnt +1);
            cnt++;
        }

        return strBuilder.toString();
    }
}

Reference

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