Squash Spaces

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 two pointers: `i` and `j`, both set to 0.
2. Create an empty `result` list to store characters.
3. While `i` is less than the length of the string:
   a. Skip leading spaces by incrementing `i`.
   b. If `i` is out of bounds, break the loop.
   c. Append the current non-space character to the `result`.
   d. Increment `i` and skip consecutive spaces.
4. Convert the `result` list back to a string and return it after stripping any leading/trailing spaces

⚠️ 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 two pointers
    i = 0
    n = len(s)
    result = []
    
    # Iterate through the string
    while i < n:
        # Skip over any leading spaces
        while i < n and s[i] == ' ':
            i += 1
        if i >= n:
            break
        
        # Append the current non-space character
        result.append(s[i])
        i += 1
        
        # If the current character was a space, skip consecutive spaces
        while i < n and s[i] == ' ':
            i += 1
    
    # Convert list back to string and strip any leading/trailing spaces
    return ''.join(result)