We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Adding Spaces to a String

Difficulty: Medium

Problem Description

You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index. Return the modified string after the spaces have been added.

Key Insights

  • The indices in the spaces array specify where to insert spaces in the string.
  • We need to ensure that the spaces are inserted in order, starting from the leftmost index.
  • The resulting string must maintain the original character order while adding the required spaces.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of the string s and m is the length of the spaces array.
Space Complexity: O(n + m) for storing the new string with spaces.

Solution

To solve the problem, we can use a two-pointer approach. One pointer will traverse the original string s, while the other will iterate through the spaces array. We will build a new string by appending characters from s and adding spaces at the specified indices. This approach ensures we efficiently handle the insertion of spaces without needing to repeatedly construct substrings.

Code Solutions

def add_spaces(s, spaces):
    result = []
    last_index = 0
    for space_index in spaces:
        # Append the substring from the last index to the current space index
        result.append(s[last_index:space_index])
        # Append a space
        result.append(' ')
        # Update last_index to the current space index
        last_index = space_index
    # Append the rest of the string after the last space index
    result.append(s[last_index:])
    return ''.join(result)
← Back to All Questions