Adjacent Duplicates Remover

Edit PagePage History

JCSU Unit 5 Problem Set 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: String Manipulation, Iteration

1: U-nderstand

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

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What is the goal of the problem?
  • Remove adjacent duplicate characters in a string and return the cleaned string.
• Are there constraints on input?
  • The input can be an empty string or contain any combination of characters.

HAPPY CASE Input: s = "aabbccdde" Output: "abcde" Explanation: Adjacent duplicates "aa", "bb", "cc", and "dd" are reduced to "a", "b", "c", and "d".

EDGE CASE Input: s = "" Output: "" Explanation: An empty string results in an empty output.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For adjacent duplicate removal problems, we want to consider the following approaches:

• Iteration and Comparison: Use a loop to compare each character with the previous one and construct a new result string.
• Two-Pointer Technique (Alternative): Traverse the string using pointers to track and remove duplicates.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Iterate through the string and compare each character with the previous one. If the current character is different from the previous one, add it to the result list.

Steps:

1. Check if the input string s is empty. If it is, return an empty string.
2. Initialize a list result with the first character of the string.
3. Iterate through the string starting from the second character:
   • Compare the current character with the previous one.
   • If they are different, append the current character to result.
4. Convert result back into a string using join() and return it.

4: I-mplement

Implement the code to solve the algorithm.

def remove_adjacent_duplicates(s):
    if not s:  # Check if the string is empty
        return ""  # Return an empty string if the input is empty

    result = [s[0]]  # Initialize the result list with the first character

    for i in range(1, len(s)):  # Iterate through the string starting from the second character
        if s[i] != s[i - 1]:  # Compare the current character with the previous one
            result.append(s[i])  # Add the current character if it's not a duplicate

    return ''.join(result)  # Join the result list into a string and return it

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

• Input: s = "aabbccdde"
• Expected Output: "abcde"
• Observed Output: "abcde"

Example 2:

• Input: s = "bookkeeper"
• Expected Output: "bokeper"
• Observed Output: "bokeper"

Example 3:

• Input: s = ""
• Expected Output: ""
• Observed Output: ""

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the length of the string.

• Time Complexity: O(n) because we iterate through the string once.
• Space Complexity: O(n) because we store the result as a new list and then convert it to a string.