[Question]: A valid parentheses string is either empty ""
, "(" + A + ")"
, or A + B
, where A
and B
are valid parentheses strings, and +
represents string concatenation.
For example, ""
, "()"
, "(())()"
, and "(()(()))"
are all valid parentheses strings.
Return s
after removing the outermost parentheses of every primitive string in the primitive decomposition of s
.
Example 1:
Input: s = "(()())(())" Output: "()()()" Explanation: The input string is "(()())(())", with primitive decomposition "(()())" + "(())". After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
Example 2:
Input: s = "(()())(())(()(()))" Output: "()()()()(())" Explanation: The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))". After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
Example 3:
Input: s = "()()" Output: "" Explanation: The input string is "()()", with primitive decomposition "()" + "()". After removing outer parentheses of each part, this is "" + "" = "".
// TC: O(n)
// SC: O(_)
func removeOuterParentheses(_ s: String) -> String {
var outputStr = ""
var opened = 0
for c in s {
if c == "(" {
if opened > 0 {
outputStr.append(c)
}
opened+=1
}
if c == ")" {
if opened > 1 {
outputStr.append(c)
}
opened-=1
}
}
return outputStr
}
let parnthString = "(()())(())"
let opRemovedLastParath = removeOuterParentheses(parnthString)
print(" removed last Paranth", opRemovedLastParath) // ()()()
Dry Run: for ( ( ) ( ) ) ( ( ) )
Input | Opened Current | Opened After | Output |
( | 0 | 1 | “” |
( | 1 | 2 | ( |
) | 2 | 1 | ( ) |
( | 1 | 2 | ( ) ( |
) | 2 | 1 | ( ) ( ) |
) | 1 | 0 | ( ) ( ) |
( | 0 | 1 | ( ) ( ) |
( | 1 | 2 | ( ) ( ) ( |
) | 2 | 1 | ( ) ( ) ( ) |
) | 1 | 0 | ( ) ( ) ( ) |