Leetcode 2109: Adding Spaces to a String

Input: You are given a string s consisting of lowercase and uppercase English letters and an array spaces where each element is an index at which a space should be inserted.

Example: s = "HelloWorld", spaces = [5]

Constraints:

• 1 <= s.length <= 3 * 10^5

• 1 <= spaces.length <= 3 * 10^5

• 0 <= spaces[i] <= s.length - 1

• The values in spaces are strictly increasing

Output: Return the string with spaces inserted before the characters at the indices specified in the array spaces.

Example: For s = "HelloWorld", spaces = [5], the output should be "Hello World".

Constraints:

Goal: The goal is to modify the string by inserting spaces at the specified indices.

Steps:

• Iterate through the string and check if the current index matches an index from the spaces array.

• If the index matches, insert a space before the current character.

• Continue processing the remaining characters in the string after inserting the spaces.

Goal: The constraints ensure that the function works efficiently even with large inputs.

Steps:

• The string length and the number of indices in spaces can be large (up to 300,000).

Assumptions:

• The input string s only contains English letters.

• The array spaces is sorted and does not contain duplicate values.

• Input: Example 1: s = "ProgrammingIsFun", spaces = [11, 14]

• Explanation: We insert spaces before 'I' at index 11 and before 'F' at index 14 to obtain the string: "Programming Is Fun".

• Input: Example 2: s = "CodingChallenges", spaces = [6, 11]

• Explanation: We insert spaces before 'C' at index 6 and before 'C' at index 11 to obtain the string: "Coding Challenges".

Approach: The approach is to process the string by adding spaces at the specified indices while maintaining the order of the original characters.

Observations:

• We can keep track of the current index and compare it to the indices in the spaces array.

• After each insertion, we can continue from the next character.

• This can be done in a single pass through the string with efficient space management.

Steps:

• Initialize an empty result string.

• Iterate through the string, checking for matches with indices in the spaces array.

• Insert spaces before the matching characters and continue to the next character in the string.

Empty Inputs:

• If the string is empty, the output should also be an empty string.

Large Inputs:

• The solution should efficiently handle the maximum input size of 300,000 characters and indices.

Special Values:

• If the spaces array contains all indices of the string, spaces will be inserted before every character.

Constraints:

• The solution should handle up to 300,000 spaces efficiently.

string addSpaces(string s, vector<int>& spaces) {
    int i = 0;
    string res = "";
    for(int idx : spaces) {
        while(i < idx) res += s[i++];
        if(i == idx) res += ' ';
    }
    while(i < s.size()) res += s[i++];        
    return res;
}

1 : Function Definition

string addSpaces(string s, vector<int>& spaces) {

Define the function `addSpaces` that takes a string `s` and a vector of integers `spaces` to insert spaces at specified positions in `s`.

2 : Variable Initialization

    int i = 0;

Initialize the index `i` to keep track of the position in the string `s`.

3 : Variable Initialization

    string res = "";

Initialize the result string `res` to store the modified string with spaces inserted.

4 : Loop Start

    for(int idx : spaces) {

Start a loop to iterate over each index in the `spaces` vector.

5 : Loop Body

        while(i < idx) res += s[i++];

Copy characters from the string `s` to `res` until the current index `idx` is reached.

6 : Condition Check

        if(i == idx) res += ' ';

When the current index `i` matches the index in `spaces`, add a space to `res`.

7 : Final Copy

    while(i < s.size()) res += s[i++];

Copy any remaining characters from `s` to `res` after the last specified space position.

8 : Return Statement

    return res;

Return the modified string `res` which now includes the spaces.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of the string, as we process each character once.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) as we construct the result string, which can be at most the length of the input string plus the number of spaces.

Leetcode 2109: Adding Spaces to a String

Explore →