[LeetCode][Kotlin] 1249. Minimum Remove to Make Valid Parentheses

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

'(' , ')' 와 영어 소문자로 구성된 문자열 s가 주어집니다. 

귀하의 작업은 결과 괄호 문자열이 유효하고 유효한 문자열을 반환하도록 최소 수의 괄호(모든 위치에서 '(' 또는 ')')를 제거하는 것입니다. 

공식적으로 괄호 문자열은 다음과 같은 경우에만 유효합니다. 
- 빈 문자열이거나 소문자만 포함하거나 
- AB(A와 B를 연결함)로 작성할 수 있습니다. 여기서 A와 B는 유효한 문자열입니다. 
- (A)로 작성할 수 있습니다. 여기서 A는 유효한 문자열입니다.

 

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 <= 10^5
• s[i] is either '(' , ')', or lowercase English letter.

---

코드 1

class Solution {
    fun minRemoveToMakeValid(s: String): String {
        val list = mutableListOf<Char>()

        var left = 0
        var right = 0
        s.forEach { c ->
            if (c == '(') {
                list.add(c)
                left++
            } else if (c == ')' && left > 0) {
                list.add(c)
                left--
                right++
            } else if (c != ')') {
                list.add(c)
            }
        }

        var answer = ""
        list.forEach { c ->
            if (c == '(') {
                if (right > 0) {
                    answer += c
                    right--
                }
            } else {
                answer += c
            }
        }

        return answer
    }
}

 

코드 2

class Solution {
    fun minRemoveToMakeValid2(s: String): String {
        val list = mutableListOf<Char>()

        var cnt = 0
        s.forEach { c ->
            if (c == '(') {
                list.add(c)
                cnt++
            } else if (c == ')' && cnt > 0) {
                list.add(c)
                cnt--
            } else if (c != ')') {
                list.add(c)
            }
        }

        val answer = mutableListOf<Char>()
        for (c in list.reversed()) {
            if (c == '(' && cnt > 0) {
                cnt--
            } else {
                answer.add(c)
            }
        }

        return answer.reversed().joinToString("")
    }
}