Content Cleaner - 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 characters should be removed from the post?
  • A: Any pairs of adjacent characters where one is the lowercase version of a letter and the other is the uppercase version of the same letter.
• Q: What is the output if the post is already clean?
  • A: The output should be the post itself.
• Q: How should an empty string be handled?
  • A: An empty string should be returned as is since it is considered clean.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to help remove adjacent character pairs that are the same letter in different cases.

1. Initialize an empty stack to hold the characters of the post.
2. Iterate through each character in the post:
   1. If the stack is not empty and the top character in the stack forms a removable pair with the current character (i.e., one is the lowercase version and the other is the uppercase version of the same letter), pop the top character from the stack.
   2. Otherwise, push the current character onto the stack.
3. After iterating through the post, the stack will contain the cleaned characters.
4. Convert the stack back into a string and return it as the cleaned post.

⚠️ Common Mistakes

• Forgetting to check for both lowercase and uppercase letter pairs.
• Not handling edge cases like an empty string or a string with no removable pairs.
• Incorrectly manipulating the stack, leading to incorrect results.

I-mplement

def clean_post(post):
    stack = []
    
    for char in post:
        if stack and (stack[-1] == char.swapcase()):
            stack.pop()  # Remove the last character since it forms a removable pair
        else:
            stack.append(char)  # Otherwise, add the current character to the stack
    
    return ''.join(stack)