Problem of The Day: Adding Spaces to a String

Problem Statement

Intuition

When I first encountered this problem, my initial thought was to treat it like a sequential insertion task where spaces are added into the string at the given indices. However, directly modifying a string while iterating over it isn’t efficient since strings are immutable in Python. Instead, I wanted to find a way to build the final string efficiently while iterating through the characters and indices.

Approach

I decided to use a two-pointer approach with a deque to build the result efficiently. Starting from the end of the string and working backwards simplifies the process because I can handle the indices from spaces in reverse order without needing to adjust them as spaces are inserted.

Here are the detailed steps:

1. Convert the string into characters and use a deque to allow efficient addition at both ends.
2. Start from the last index of the string and the last space position, iterating backwards.
3. For each space index, append characters to the deque until the current space index is reached, then append a space.
4. After all spaces are handled, append any remaining characters from the start of the string.
5. Finally, join the characters in the deque to form the resulting string.

This approach ensures that we don’t have to repeatedly modify the string, leading to a more efficient solution.

Complexity

• Time complexity:
  \(O(n)\)
  The algorithm processes each character in the string exactly once and handles each index in spaces exactly once.

• Space complexity:
  \(O(n)\)
  The deque stores the characters of the string, so its size grows linearly with the length of the string.

Code

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        s_idx = len(s) - 1
        list_chars = deque()
        while spaces:
            curr_idx = spaces.pop()
            while s_idx >= curr_idx:
                list_chars.appendleft(s[s_idx])
                s_idx -= 1
            list_chars.appendleft(' ')
        for i in range(s_idx, -1, -1):
            list_chars.appendleft(s[i])
        return ''.join(list_chars)

Editorial

Approach 1: Using Built-in Functions

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        # List to store characters (more efficient than string concatenation)
        result = []
        space_index = 0

        for string_index in range(len(s)):
            if (
                space_index < len(spaces)
                and string_index == spaces[space_index]
            ):
                # Insert space at the correct position
                result.append(" ")
                space_index += 1

            # Append the current character
            result.append(s[string_index])

        # Join all characters into final string
        return "".join(result)

Approach 2: Two-Pointer Technique

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        result = []
        # Pre-allocate approximate space for efficiency
        result = [None] * (len(s) + len(spaces))

        space_index = 0
        string_index = 0

        for char_index in range(len(s)):
            if space_index < len(spaces) and char_index == spaces[space_index]:
                # Insert space at the correct position
                result[string_index] = " "
                string_index += 1
                space_index += 1

            # Append the current character
            result[string_index] = s[char_index]
            string_index += 1

        # Join the list into a string and return only the used portion
        return "".join(result[:string_index])