Rearrange Animals and Slogans - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What is the input to the problem?
    • A: The input is a string s consisting of lowercase English letters and parentheses.
  • Q: What is the output?
    • A: The output is the string s with the contents inside each pair of matching parentheses reversed, starting from the innermost pair, with all parentheses removed.
  • Q: How should the parentheses be handled?
    • A: The innermost pair of parentheses should be processed first, reversing the string inside, and then proceeding outward until all parentheses are removed.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to reverse the substrings enclosed in parentheses, starting with the innermost pair. When a closing parenthesis is encountered, reverse the substring within the most recent opening parenthesis and then remove the parentheses.

1. Initialize an empty stack to keep track of characters as they are processed.
2. Iterate through each character in the string `s`:
   1. If the character is a closing parenthesis `)`, start reversing the contents within the most recent opening parenthesis:
      * Pop characters from the stack until an opening parenthesis `(` is found.
      * Reverse the characters popped and push them back onto the stack.
   2. If the character is not a closing parenthesis, push it onto the stack.
3. After processing all characters, the stack will contain the final string with all parentheses removed and all required reversals applied.
4. Convert the stack into a string and return it.

⚠️ Common Mistakes

  • Forgetting to remove the opening parenthesis from the stack after processing a closing parenthesis.
  • Not handling nested parentheses correctly, leading to incorrect reversals.
  • Mismanaging the order of characters when reversing the string inside the parentheses.

I-mplement

def rearrange_animal_names(s):
    stack = []
    for char in s:
        if char == ')':
            rev = ""
            while stack and stack[-1] != '(':
                rev += stack.pop()
            if stack:
                stack.pop()  # pop the opening parenthesis
            for c in rev:
                stack.append(c)
        else:
            stack.append(char)

    return ''.join(stack)

print(rearrange_animal_names("(dribtacgod)"))  # Output: "dogcatbird"
print(rearrange_animal_names("(!(love(stac))I)"))  # Output: "Ilovecats!"
print(rearrange_animal_names("adopt(yadot(a(tep)))!"))  # Output: "adoptapettoday!"