Leetcode daily question (2109. adding spaces to a string)

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” and spaces = [5, 9], we place spaces before ‘Y’ and ‘C’, which are at indices 5 and 9 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.

---

Suppose you are currently inserting index by i, Currently, we have inserted n There are two spaces , What actually needs to be inserted index It becomes i + n
however rust It takes more than a second to complete the whole with this method , Possible and String The underlying implementation is related to , Once the allocated capacity of the current string is exceeded , That insertion requires a reallocation of memory , But I don't know how often this reallocation will happen , It should not be reallocated every time you insert . Use it another day split Then do it again by splicing , See if the speed will be faster

---

impl Solution {
    
    pub fn add_spaces(mut s: String, spaces: Vec<i32>) -> String {
    
        let mut added = 0;
        for si in spaces {
    
            s.insert(si as usize + added, ' ');
            added += 1;
        }
        s
    }
}