Problem
Given a string s and a list of words (all the same length), find all starting indices in s of substrings that concatenate every word exactly once.
Example
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]Solution
For each starting position, check if the next n*wordLen chars contain each word exactly once.
def find_substring(s, words):
if not words: return []
word_len = len(words[0])
total = word_len * len(words)
word_count = {}
for w in words: word_count[w] = word_count.get(w, 0) + 1
result = []
for i in range(len(s) - total + 1):
seen = {}
for j in range(len(words)):
word = s[i + j * word_len : i + (j + 1) * word_len]
if word not in word_count: break
seen[word] = seen.get(word, 0) + 1
if seen[word] > word_count[word]: break
else:
result.append(i)
return resultfunction findSubstring(s, words) {
if (!words.length) return [];
const wordLen = words[0].length;
const total = wordLen * words.length;
const wordCount = {};
for (const w of words) wordCount[w] = (wordCount[w] || 0) + 1;
const result = [];
for (let i = 0; i <= s.length - total; i++) {
const seen = {};
let valid = true;
for (let j = 0; j < words.length; j++) {
const word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
if (!(word in wordCount)) { valid = false; break; }
seen[word] = (seen[word] || 0) + 1;
if (seen[word] > wordCount[word]) { valid = false; break; }
}
if (valid) result.push(i);
}
return result;
}vector<int> findSubstring(string s, vector<string>& words) {
vector<int> result;
if (words.empty()) return result;
int wordLen = words[0].size();
int total = wordLen * words.size();
unordered_map<string, int> wordCount;
for (auto& w : words) wordCount[w]++;
for (int i = 0; i + total <= s.size(); i++) {
unordered_map<string, int> seen;
bool valid = true;
for (int j = 0; j < words.size(); j++) {
string word = s.substr(i + j * wordLen, wordLen);
if (!wordCount.count(word)) { valid = false; break; }
if (++seen[word] > wordCount[word]) { valid = false; break; }
}
if (valid) result.push_back(i);
}
return result;
}public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (words.length == 0) return result;
int wordLen = words[0].length();
int total = wordLen * words.length;
Map<String, Integer> wordCount = new HashMap<>();
for (String w : words) wordCount.merge(w, 1, Integer::sum);
for (int i = 0; i + total <= s.length(); i++) {
Map<String, Integer> seen = new HashMap<>();
boolean valid = true;
for (int j = 0; j < words.length; j++) {
String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
if (!wordCount.containsKey(word)) { valid = false; break; }
seen.merge(word, 1, Integer::sum);
if (seen.get(word) > wordCount.get(word)) { valid = false; break; }
}
if (valid) result.add(i);
}
return result;
}Complexity
- Time: O(n * m * k)
- Space: O(m)
Explanation
n = length of s, m = number of words, k = word length. For each starting position, we walk through m words to check the match.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?