Problem Statement in English

You’re given a string s and an array of integers spaces.

The string s will be modified by adding a space before the character at each index specified in spaces.

For example, if s = "hello" and spaces = [1, 3], then the modified string will be "h e llo".

Approach

We can use two pointers to solve this problem.

One pointer will traverse the string s and the other pointer will traverse the spaces array.

We will maintain a stack to build the modified string.

At each step, we will check if the current index of the string matches the current index in the spaces array. If it does, we will add a space to the stack and move the pointer for spaces forward.

Then we will add the current character from the string to the stack and move the pointer for the string forward.

Finally, we will join the stack to get the modified string.

And we’re done!

Solution in Python


class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        p1 = p2 = 0

        stack = []

        while p1 < len(s):
            if p2 < len(spaces) and p1 == spaces[p2]:
                stack.append(" ")
                p2 += 1
            stack.append(s[p1])
            p1 += 1

        return "".join(stack)

Complexity

  • Time: $O(n + m)$
    Since we traverse the string and the spaces array once.

  • Space: $O(n + m)$
    Since we store the result in a stack.

And we are done.