How hard is LeetCode 2109. Adding Spaces to a String?

LeetCode 2109. Adding Spaces to a String is rated Medium on LeetCode.

What is the time complexity of LeetCode 2109. Adding Spaces to a String?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 2109. Adding Spaces to a String?

The Python solution on this page uses O(n + m), where n and m are the lengths of the string s and the array spaces, respectively auxiliary space.

What topics does LeetCode 2109. Adding Spaces to a String cover?

LeetCode 2109. Adding Spaces to a String is tagged Array, Two Pointers, String and Simulation on LeetCode.

Adding Spaces to a String — LeetCode 2109 Python Solution

MediumArrayTwo PointersStringSimulation

Problem: #2109
Pattern: Two Pointers
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
Output: "Leetcode Helps Me Learn"
Explanation: The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn".

Python solution

Python

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        ans = []
        j = 0
        for i, c in enumerate(s):
            if j < len(spaces) and i == spaces[j]:
                ans.append(' ')
                j += 1
            ans.append(c)
        return ''.join(ans)

Complexity

Measure	Complexity
Time	O(n + m)
Space	O(n + m), where n and m are the lengths of the string s and the array spaces, respectively auxiliary

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2109. Adding Spaces to a String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2109. Adding Spaces to a String?: LeetCode 2109. Adding Spaces to a String is rated Medium on LeetCode.
What is the time complexity of LeetCode 2109. Adding Spaces to a String?: The Python solution on this page runs in O(n + m).
What is the space complexity of LeetCode 2109. Adding Spaces to a String?: The Python solution on this page uses O(n + m), where n and m are the lengths of the string s and the array spaces, respectively auxiliary space.
What topics does LeetCode 2109. Adding Spaces to a String cover?: LeetCode 2109. Adding Spaces to a String is tagged Array, Two Pointers, String and Simulation on LeetCode.