30. Substring with Concatenation of All Words

📝 Problem Details

• Title: 30. Substring with Concatenation of All Words
• Link: https://leetcode.com/problems/substring-with-concatenation-of-all-words/
• Difficulty: Hard
• Tags/Categories: Strings Hashmap Two-Pointers Sliding-Window

💭What Were My Initial Thoughts?

- sliding window 
- third example best illustrates how to solve the problem
- visualising the window helps in this problem 

🤔What Did I Struggle With?

- resetting the window at the correct position to account for multiple start indexes inside a window

💡 Explanation of Solution

- create a hashmap wordCount to store the frequency of each word in the given list of words 
- calculate the length of each word (wordLength)
- calculate the total concatenated length of all words (substringLength = wordLength * words.size())

- iterate over start points
	- since the words have fixed lengths, iterate the string in wordLength chunks using indices i in range 0 - words.size()

- sliding window 
	- use two pointers , start and end, to maintain a sliding window of length equal to substringLength
	- track words within the window using a hashmap currentCount

- expand the window 
	- slide end by wordLength chunks, extract the word in the substring, and check:
		- if the word is in wordCount, add it to the currentCount and check:
			- if currentCount[word] > wordCount[word], it means there's an extra word, so shrink the window from start until the condition is valid
			- if end - start == substring.size(), store start as a valid index 
		- if the word is not in wordCount, reset currentCount and move start to end 

- adjust start for overlaps:
	- if an invalid word is found or the window size exceeds substring.size(), move the start to end and reset the currentCount

- collect results:
	- append valid start indices to the result list 

⌛ Complexity Analysis

Time Complexity: 
- n is the length of the string s
- each shift through the length of the string is in k chunks where k is the length of the word in the words array

Space Complexity: O(m)
- m is the number of unique words in words for storage of frequency counts in the hashmap 

💻 Implementation of Solution

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        if (s.empty() || words.empty()) return result;
        
        int word_length = words[0].length();
        int substring_length = word_length * words.size();
        unordered_map<string, int> word_count;
        
        // Count the frequency of each word in the words array
        for (const string& word : words) {
            word_count[word]++;
        }
        
        // Sliding window over `word_length` shifts
        for (int i = 0; i < word_length; ++i) {
            unordered_map<string, int> current_count;
            int start = i, end = i;
            
            while (end + word_length <= s.length()) {
                string word = s.substr(end, word_length);
                end += word_length;
                
                if (word_count.find(word) != word_count.end()) {
                    current_count[word]++;
                    
                    // If word frequency exceeds the allowed count, shrink the window
                    while (current_count[word] > word_count[word]) {
                        string left_word = s.substr(start, word_length);
                        current_count[left_word]--;
                        start += word_length;
                    }
                    
                    // If window size matches substring length, record the starting index
                    if (end - start == substring_length) {
                        result.push_back(start);
                    }
                } else {
                    // Invalid word, reset the window
                    current_count.clear();
                    start = end;
                }
            }
        }
        
        return result;
    }
};