2109. Adding Spaces to a String
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.
- For example, given
s = "EnjoyYourCoffee"
andspaces = [5, 9]
, we place spaces before'Y'
and'C'
, which are at indices5
and9
respectively. Thus, we obtain"Enjoy Your Coffee"
.
Return the modified string after the spaces have been added.
Example 1:
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". We then place spaces before those characters.
Example 2:
Input: s = "icodeinpython", spaces = [1,5,7,9] Output: "i code in py thon" Explanation: The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython". We then place spaces before those characters.
Example 3:
Input: s = "spacing", spaces = [0,1,2,3,4,5,6] Output: " s p a c i n g" Explanation: We are also able to place spaces before the first character of the string.
Constraints:
1 <= s.length <= 3 * 105
s
consists only of lowercase and uppercase English letters.1 <= spaces.length <= 3 * 105
0 <= spaces[i] <= s.length - 1
- All the values of
spaces
are strictly increasing.
Solutions
Solution 1: Two Pointers
We can use two pointers $i$ and $j$ to point to the beginning of the string $s$ and the array $\textit{spaces}$, respectively. Then, we iterate through the string $s$ from the beginning to the end. When $i$ equals $\textit{spaces}[j]$, we add a space to the result string, and then increment $j$ by $1$. Next, we add $s[i]$ to the result string, and then increment $i$ by $1$. We continue this process until we have iterated through the entire string $s$.
The time complexity is $O(n + m)$, and the space complexity is $O(n + m)$, where $n$ and $m$ are the lengths of the string $s$ and the array $spaces$, respectively.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|