1021.remove-outermost-parentheses.md

1021. Remove Outermost Parentheses

Counting

We maintain a left parenthsis count, it will be the outermost when:

1. It's the first left parenthsis. it's the left parenthsis that makes the count 0 -> 1.
2. It's the last left parenthsis, it's the right parenthsis that makes the count 1 -> 0.

If it's not the outermost, we append it to the result.

fun removeOuterParentheses(s: String): String {
    var leftCount = 0
    val result = StringBuilder()
    for (c in s) {
        if (c == '(') {
            if (leftCount > 0) result.append(c.toString())
            leftCount++
        } else {
            leftCount--
            if (leftCount > 0) result.append(c.toString())
        }
    }
    return result.toString()
}

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(1), where we don't count the space for the result.

Stack

Might skip this solution, it's overcomplicated.

fun removeOuterParentheses(s: String): String {
    val ans = StringBuilder()
    val stack = Stack<String>()
    for (c in s) {
        if (c == '(') {
            stack.push(c.toString())
        } else {
            val str = LinkedList<String>()
            while (stack.isNotEmpty() && stack.peek() != "(") {
                str.addFirst(stack.pop())
            }
            stack.pop() // Pop (
            if (stack.isNotEmpty()) {
                str.addLast(")")
                str.addFirst("(") 
                stack.push(str.joinToString(""))
            } else { // It's outermost, add current string to answer
                ans.append(str.joinToString(""))
            }
        }
    }
    return ans.toString()
}