LeetCode Solutions Blog

Adding Spaces to a String

Number: 2232

Difficulty: Medium

Paid? No

Problem Description

Given a string s and an array spaces, insert a space before each character in s at the indices specified in spaces. Return the modified string after all the spaces have been added.

Key Insights

Use the fact that spaces is sorted in strictly increasing order.
Traverse the string with a pointer while using another pointer (or index) to track the current space index.
Insert a space into the result string every time the current string index matches the next index in the spaces array.
Efficiently build the result string ensuring minimal additional space overhead.

Space and Time Complexity

Time Complexity: O(n) where n is the length of s, because each character is processed once. Space Complexity: O(n) to store the final resulting string.

Solution

We use two pointers: one for iterating through the string and one for the spaces array. At each step, if the current index equals the next space index, we append a space before appending the character. This process continues until the end of the string is reached. The sorted nature of the spaces array enables efficient linear traversal.

Code Solutions

# Define a function to add spaces to the input string as specified by the sorted spaces array.
def addSpaces(s: str, spaces: [int]) -> str:
    # Initialize an empty list to collect parts of the result string.
    result = []
    # Pointer for the spaces array.
    space_index = 0
    # Iterate over each character index in the string.
    for i, char in enumerate(s):
        # Check if the current index i matches the next space position.
        if space_index < len(spaces) and i == spaces[space_index]:
            # Append a space to the result.
            result.append(" ")
            # Move to the next space index.
            space_index += 1
        # Append the current character.
        result.append(char)
    # Join the list into a single string and return.
    return "".join(result)

# Example usage:
print(addSpaces("LeetcodeHelpsMeLearn", [8, 13, 15]))