RECUR30 - Editorial

Problem Link - Flatten String in Recursion

Problem Statement:

You are given a string that may contain nested parentheses, each with inner strings. The goal is to write a recursive function, flatten_string, that flattens the given string by removing all parentheses and concatenating the characters in the nested structure.

Approach:

1. Character by Character Traversal:

  • We traverse the string one character at a time.
  • For each character, we check whether it’s an opening parenthesis (, closing parenthesis ), or just a regular letter.

2. Handling Parentheses:

  • Opening Parenthesis (:
    • When we find (, it means we’re entering a nested section.
    • We then recursively call our function to handle everything inside this new section, until we hit the closing parenthesis ).
    • The result from the nested section is appended to our main result.
  • Closing Parenthesis ):
    • When we find ), it means we’re done with this section, so we stop the current recursive call and return the result we’ve collected so far.

3. Regular Characters: Any letter that’s not inside parentheses is added directly to our result string.

4. Edge Case: If there are no parentheses, the function will just go through the string and return it unchanged.

Complexity:

  • Time Complexity: O(n) where n is the length of the string. Each character is processed exactly once.
  • Space Complexity: O(n) due to the recursion stack, especially for deeply nested parentheses.