2109. Adding Spaces to a String

📝 Problem Details

• Title: 2109. Adding Spaces to a String
• Link: https://leetcode.com/problems/adding-spaces-to-a-string/
• Difficulty: Medium
• Tags/Categories: Hashmap Strings Two-Pointers

💭What Were My Initial Thoughts?

- insert all of the indices into a hashset
- iterate through the input string and check if our current iterator exists in the hashset
- if it does, insert a space
- insert the character in s[i] regardless of the above check
- return the new string

🤔What Did I Struggle With?

- i didnt ask if the spaces vector was sorted
	- if i did, i wouldve known a two-pointers approach couldve worked, saving the need to employ auxilary space to solve the problem

💡 Explanation of Solution

Hashset Solution is explained above (viable)

Two-Pointer approach:
- pointer (i) iterates through the main string s
- pointer (j) keeps track of positions in the spaces vector
	- only advance this counter and insert a space when j is inbounds and i == spaces[j]
- insert the character s[i] into the new string for every iteration of i

⌛ Complexity Analysis

Hashset Solution
	Time Complexity: O(n) where n is the length of the input string s
	Space Complexity: O(n) since we are storing up to n indexes in our hashset

Two-Pointer Solution:
	Time Complexity: O(n) where n is the length of the input string s
	Space Complexity: O(1) since we are not utilising any additional space to solve the problem 
--

💻 Implementation of Solution (Hashmap)

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        unordered_set<int> set(spaces.begin(), spaces.end());
        string newString= "";
 
        for(int i=0; i < s.size(); i++) {
            if(set.find(i) != set.end()){
                newString += " ";
            }
            newString += s[i];
        }
        return newString;
    }
};

💻 Implementation of Solution (Two-Pointers)

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        string newString;
        int j = 0; // Pointer for the spaces array
        for (int i = 0; i < s.size(); i++) {
            if (j < spaces.size() && i == spaces[j]) { // Check bounds for j
                newString += " "; // Add a space if current index matches
                j++; // Move to the next space
            }
            newString += s[i]; // Add the current character
        }
        return newString;
    }
};