Squash Spaces - codepath/compsci_guides GitHub Wiki

Unit 4 Session 1 (Click for link to problem statements)

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Strings, Two-Pointer Technique

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 function?

  • A: The input is a string s that may contain spaces between words, including leading and trailing spaces.

• Q: What is the expected output of the function?

  • A: The function should return a new string where consecutive spaces are reduced to a single space, and the string is trimmed of any leading or trailing spaces.

• Q: How should the function handle a string with no spaces?

  • A: If there are no spaces in the string, the function should return the original string.

• Q: What should the function return if the string contains only spaces?

  • A: The function should return an empty string.

• The function squash_spaces() should reduce consecutive spaces in the input string to a single space while trimming any leading or trailing spaces.

HAPPY CASE
Input: "   Up,     up,   and  away! "
Expected Output: "Up, up, and away!"

UNHAPPY CASE
Input: "With great power comes great responsibility."
Expected Output: "With great power comes great responsibility."

EDGE CASE
Input: "       "
Expected Output: "

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two pointers to traverse the string, appending characters to the result list while skipping consecutive spaces.

1. Initialize a pointer `ptr` to 0 (this will read through the input string).
2. Create an empty list `output` to store the result characters.
3. Skip initial spaces:
  a. While `ptr` is less than the length of the string `s` and `s[ptr]` is a space:
    i. Increment `ptr`.
4. Iterate through the string `s` while `ptr` is less than the length of `s`:
  a. If the current character is not a space:
    i. Append `s[ptr]` to `output`. 
  b. If the current character is a space:
    i. Check if `output` is not empty and the last character in `output` is not a space.
    ii. Also, ensure there is a non-space character following the current space.
    iii. If both conditions are met, append a single space to `output`.
  c. Increment `ptr` by 1.
5. Convert the `output` list to a string:
  a. Join the characters in the `output` list to form the final result string.
6. Return the final result string.

⚠️ Common Mistakes

• Forgetting to check for boundaries when accessing string indices.
• Not handling leading or trailing spaces properly.

I-mplement

Implement the code to solve the algorithm.

def squash_spaces(s):
    # Initialize pointers and the output list
    ptr = 0
    output = []

    # Skip initial spaces
    while ptr < len(s) and s[ptr] == ' ':
        ptr += 1

    while ptr < len(s):
        if s[ptr] != ' ':
            # Add non-space characters directly to output
            output.append(s[ptr])
        else:
            # Add a space only if the last added character is not a space
            # and there are more characters after the current one
            if len(output) > 0 and output[-1] != ' ' and ptr + 1 < len(s) and s[ptr + 1] != ' ':
                output.append(s[ptr])

        ptr += 1

    # Join list into a final string
    return ''.join(output)