Remove Outermost Parentheses - Leetcode Solution

Problem Statement: 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. A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings. Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + ... + P_k, where P_i are primitive valid parentheses strings. Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

Example: Input: "(()())(())" Output: "()()()"

Explanation: The input string has primitive decomposition "(()())" + "(())". After removing outer parentheses of each part, this is "()()" + "()", which equals "()()()".

Solution:

Approach: We need to remove the outermost parentheses of every primitive string in the given string.

We can solve this by traversing the given string and keeping track of the parentheses count. Whenever we encounter an opening parentheses, we increase the count, and whenever we encounter a closing parentheses, we decrease the count. We remove the parentheses if the parentheses count becomes zero.

Algorithm:

1. Define an empty string called result.
2. Define a variable called openingCount, initialized as zero.
3. Traverse the input string from the left to the right: a. If the current character is '(', increment openingCount. b. If the current character is ')', decrement openingCount. c. If openingCount is zero and the current character is a ')' or the length of the string is reached, remove the outermost parentheses of the current primitive string and add the result to the result string.
4. Return the result string.

Code in Python:

class Solution: def removeOuterParentheses(self, S: str) -> str: result = "" openingCount = 0 primitiveStartIndex = 0

    for i in range(len(S)):
        if(S[i] == '('):
            openingCount += 1
        else:
            openingCount -= 1

        if(openingCount == 0):
            primitiveString = S[primitiveStartIndex:i+1]
            result += primitiveString[1:-1]
            primitiveStartIndex = i+1

    return result

Time complexity: O(n), where n is the length of the given string. Space complexity: O(n), to store the result string.

This algorithm provides a solution for the given problem statement on LeetCode.

1