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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 3 * 105
	s consists only of lowercase and uppercase English letters.
	1 &lt;= spaces.length &lt;= 3 * 105
	0 &lt;= spaces[i] &lt;= s.length - 1
	All the values of spaces are strictly increasing.


#TLE SOLUTION
class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
		spaces_idx = len(spaces)-1

		def addString(index,s):
			s = s[:index]+" "+s[index:] 
			#This changes the string at every instance hence taking so much time
			return s
			
		while spaces_idx>=0:
			s = addString(spaces[spaces_idx],s)
			spaces_idx-=1
		return s
class Solution {
    public String addSpaces(String s, int[] spaces) {
        
        int j = 0,curr = 0;
        StringBuilder sb = new StringBuilder();
        while(curr<s.length()){
           
             if(j<spaces.length&&spaces[j]==curr){
                 
                sb.append(" ");
                j++;
    
                }
                sb.append(s.charAt(curr));
                curr++;

        }

        return sb.toString();
        
    }
}
class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        
        int i,n=spaces.size(),m=s.size(),j;
        string ans="";
        i=0;
        j=0;
        
        //jth pointer for current index of spaces vector
        //ith pointer for current index of our answer string
        while(i<m)
        {
            //if at our current index i is equals to spaces[j] which means we have space at this index,so we add space right here
            if(j<n&&i==spaces[j])
            {
                ans+=" ";
                j++;
                //incrementing j to get next space index location
            }
            ans+=s[i];
            i++;
        }
        
        return ans;
    }
};
/**
 * @param {string} s
 * @param {number[]} spaces
 * @return {string}
 */
var addSpaces = function(s, spaces) {
    let words = spaces.map((space, index) => s.slice(index == 0 ? 0 : spaces[index-1], space));
    words.push(s.slice(spaces[spaces.length-1]));
    return words.join(' ');
};
Adding Spaces to a String