Interview Classic 150 Questions P30 Substring with Concatenation of All Words

---

Timeline

Timeline

2025-11-13

init

Sliding window

---

Problem:

P30 Substring with Concatenation of All Words

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150

Note that starting from the first letter of s is different from starting from the second letter, so the sliding window algorithm needs to run words[0].size times.

#include <vector>
#include <unordered_map>
#include <string>

using std::string;
using std::unordered_map;
using std::vector;

class Solution {
    public:
	vector<int> findSubstring(string s, vector<string> &words)
	{
		vector<int> result;
		if (s.empty() || words.empty())
			return result;

		int word_len = words[0].size();
		int num_words = words.size();
		int total_len = word_len * num_words;
		int n = s.size();

		unordered_map<string, int> word_count;
		for (auto &w : words)
			word_count[w]++;

		for (int i = 0; i < word_len; ++i) { // 0..word_len to avoid missing
			int left = i, right = i;
			unordered_map<string, int> curr_count;

			while (right + word_len <= n) {
				string word = s.substr(right, word_len);
				right += word_len;
				if (word_count.count(word)) {
					curr_count[word]++;
					// If a word appears more than required, the left side of the window needs to be shrunk.
					while (curr_count[word] > word_count[word]) {
						string left_word = s.substr(left, word_len);
						curr_count[left_word]--;
						left += word_len;
					}
					// Check whether the window satisfies the total length.
					if (right - left == total_len) {
						result.push_back(left);
					}
				} else {
					// If a word not in words is encountered, reset the window.
					curr_count.clear();
					left = right;
				}
			}
		}

		return result;
	}
};