2109.Adding Spaces to a String.md

Difficulty	Source	Tags
Medium	Daily-Question (POTD 3-Dec)	Array Two Pointers String Simulation

🚀 2109 - Adding Spaces to a String 🧠

Problem Link:

LeetCode - Adding Spaces to a String

💡 Problem Breakdown:

You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices where spaces will be added in the original string. Each space should be inserted before the character at the given index.

For example, if s = "EnjoyYourCoffee" and spaces = [5, 9], spaces should be inserted before the characters at indices 5 and 9, resulting in "Enjoy Your Coffee".

The task is to return the modified string after all the spaces have been added.

🔍 Example Walkthrough:

Example 1:

Input:
s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
Output:
"Leetcode Helps Me Learn"

Explanation:

• At index 8, insert a space before "H", resulting in "Leetcode HelpsMeLearn".
• At index 13, insert a space before "M", resulting in "Leetcode Helps MeLearn".
• At index 15, insert a space before "L", resulting in "Leetcode Helps Me Learn".

Example 2:

Input:
s = "icodeinpython", spaces = [1,5,7,9]
Output:
"i code in py thon"

Explanation:

• At index 1, insert a space before "c", resulting in "i codeinpython".
• At index 5, insert a space before "i", resulting in "i code inpython".
• At index 7, insert a space before "p", resulting in "i code in python".
• At index 9, insert a space before "t", resulting in "i code in py thon".

Example 3:

Input:
s = "spacing", spaces = [0,1,2,3,4,5,6]
Output:
" s p a c i n g"

Explanation:

• Spaces are inserted before every character of the string, giving the result " s p a c i n g".

Constraints:

• $1 <= s.length <= 3 * 10^5$
• s consists only of lowercase and uppercase English letters.
• $1 <= spaces.length <= 3 * 10^5$
• 0 <= spaces[i] <= s.length - 1
• All the values of spaces are strictly increasing.

🎯 My Approach:

To solve this problem, we need to insert spaces at the indices specified in the spaces array in an efficient manner. Here's how we can approach this:

1. Iterate through the string: We can process the string and use the spaces array to determine where to insert spaces.

2. Insert spaces efficiently: By using a list (instead of directly modifying the string), we can append characters and spaces in the correct positions.

3. Use a pointer for the spaces array: We use a pointer to track the positions in the spaces array, and insert spaces at the appropriate positions as we traverse the string.

4. Time complexity considerations: Since string manipulations in Python (or other languages like C++) are costly when done repeatedly, it's important to avoid repeated string concatenation. Instead, we can build the result by using a list and later joining the list into a final string.

🕒 Time Complexity:

• O(n + m):
  The time complexity is O(n + m) where n is the length of the string s and m is the length of the spaces array. We process each character of s once, and we insert spaces at the positions specified in the spaces array, which has at most n elements.

• Space Complexity:
  O(n + m): The space complexity is dominated by the space required to store the result, which consists of the characters in the string and the spaces inserted.

📝 Solution Code

Code (C):

char* addSpaces(char* s, int* spaces, int spacesSize) {
    int n = strlen(s);
    int m = spacesSize;
    char* result = (char*)malloc(n + m + 1);  

    int i = 0, j = 0, resultIndex = 0;
    while (i < n) {
        if (j < m && i == spaces[j]) {
            result[resultIndex++] = ' ';  
            j++;
        }
        result[resultIndex++] = s[i++]; 
    }

    result[resultIndex] = '\0';  
    return result;
}

Code (C++)

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        int n = s.length();
        int m = spaces.size();
        string result;
        result.reserve(n + m);  

        int spaceIndex = 0;
        for (int i = 0; i < n; ++i) {
            if (spaceIndex < m && i == spaces[spaceIndex]) {
                result.push_back(' ');  
                ++spaceIndex;
            }
            result.push_back(s[i]);  
        }

        return result;
    }
};

Code (Java)

class Solution {
    public String addSpaces(String s, int[] spaces) {
        int n = s.length();
        int m = spaces.length;
        StringBuilder result = new StringBuilder(n + m);

        int spaceIndex = 0, strIndex = 0;
        for (int i = 0; i < n; i++) {
            if (spaceIndex < m && i == spaces[spaceIndex]) {
                result.append(' ');
                spaceIndex++;
            }
            result.append(s.charAt(i));
        }

        return result.toString();
    }
}

Code (Python)

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        result = []
        prev = 0
        
        for space in spaces:
            result.append(s[prev:space])
            result.append(" ")
            prev = space
        
        result.append(s[prev:])
        return ''.join(result)

Code (Rust)

impl Solution {
    pub fn add_spaces(s: String, spaces: Vec<i32>) -> String {
        let mut result = String::with_capacity(s.len() + spaces.len());
        let bytes = s.as_bytes(); 
        let mut space_iter = spaces.into_iter();
        let mut next_space = space_iter.next();

        let mut i = 0;
        while i < bytes.len() {
            if let Some(pos) = next_space {
                if i == pos as usize {
                    result.push(' ');
                    next_space = space_iter.next();
                }
            }
            result.push(bytes[i] as char);
            i += 1;
        }

        result
    }
}

🎯 Contribute or Ask Questions:

For more discussions, questions, or help with the solution, feel free to reach out on LinkedIn: Connect with Me!.

Enjoying the Solution?

If this helped you, please star this repo to support the efforts and keep it growing!