Remove All Adjacent Duplicate Shows - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Standard (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 schedule where each character represents a different show in the lineup.
• Q: What is the output?
  • A: The output is the final schedule after all adjacent duplicate shows have been removed.
• Q: How should duplicates be removed?
  • A: Remove two adjacent and equal characters from the string. Repeat this process until no further adjacent duplicates exist.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to manage the removal of adjacent duplicate shows. Push characters onto the stack, and if the top of the stack matches the current character, pop the stack.

1. Initialize an empty stack to keep track of the characters.
2. Iterate through each character in the `schedule` string:
   1. If the stack is not empty and the top character of the stack is the same as the current character, pop the stack (remove the duplicate pair).
   2. If the top character is not the same as the current character, push the current character onto the stack.
3. After processing all characters, the stack will contain the final schedule without adjacent duplicates.
4. Convert the stack back to a string and return it as the final schedule.

⚠️ Common Mistakes

• Not considering all possible adjacent pairs, leading to incomplete removal.
• Forgetting to join the stack into a string before returning the final result.
• Mishandling edge cases like an empty string or a string with no duplicates.

I-mplement

def remove_duplicate_shows(schedule):
    # Initialize an empty stack
    stack = []
    
    # Iterate through each show in the schedule
    for show in schedule:
        # If the stack is not empty and the top element of the stack is the same as the current show, pop it
        if stack and stack[-1] == show:
            stack.pop()
        else:
            # Otherwise, push the current show onto the stack
            stack.append(show)
    
    # Convert the stack back to a string to get the final schedule
    return ''.join(stack)