algoadvance

Leetcode 1021. Remove Outermost Parentheses

Problem Statement

Given a valid parentheses string, s, you need to remove the outermost parentheses of every primitive string in the primitive decomposition of s. A primitive string is a non-empty string that cannot be split into two non-empty valid parentheses strings.

Example

Clarifying Questions

  1. What is the length constraint of the string s?
    • The length of s will be between 1 and 10,000.
  2. Is the input always guaranteed to be a valid parentheses string?
    • Yes, the input is always guaranteed to be a valid parentheses string.

Strategy

The goal is to iterate through the string while maintaining a counter to track the nesting level of the parentheses to identify the outermost ones. Here’s the approach step-by-step:

  1. Initialization:
    • Create a variable count to keep track of the balance between ( and ).
    • Use a string result to store the modified string without the outermost parentheses.
  2. Iteration:
    • Loop through each character in the string s.
    • If the current character is (:
      • If count is greater than 0, append ( to the result (indicating it’s not the outermost ().
      • Increment count.
    • If the current character is ):
      • Decrement count.
      • If count is greater than 0, append ) to the result (indicating it’s not the outermost )).
  3. The balancing of the count variable ensures that we correctly identify the outermost parentheses in each primitive segment.

Code

#include <string>
using namespace std;

class Solution {
public:
    string removeOuterParentheses(string s) {
        string result = "";
        int count = 0;

        for (char c : s) {
            if (c == '(') {
                if (count > 0) {
                    result += c;
                }
                count++;
            } else {
                count--;
                if (count > 0) {
                    result += c;
                }
            }
        }

        return result;
    }
};

Time Complexity

The time complexity of the provided solution is O(n), where n is the length of the string s. This is because we only iterate over the string once.

The space complexity is O(n) as well due to storing the resultant string without the outermost parentheses.

If there are any further questions or unclear points, feel free to ask!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI