Description:
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.
- For example, if
words = ["ab","cd","ef"], then"abcdef","abefcd","cdabef","cdefab","efabcd", and"efcdab"are all concatenated strings."acdbef"is not a concatenated string because it is not the concatenation of any permutation ofwords.
Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Examples:
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation:
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation:
There is no concatenated substring.
Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation:
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"].
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"].
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].Solution in Python:
To solve the problem of finding all starting indices of concatenated substrings in a given string s that exactly contain all strings from a list words, we need a clear and efficient approach.
Plan:
- Initial Checks:
- If the string
sor the listwordsis empty, return an empty list. - Calculate the length of each word (
word_len), the number of words (num_words), and the total length of the concatenated substring (concat_len).
- If the string
- Sliding Window Approach:
- Use a sliding window of size
concat_lento traverse through the strings. - For each starting point, check if the substring starting at that point can be formed by concatenating all the words in
words.
- Use a sliding window of size
- Word Frequency Count:
- Use a dictionary to store the frequency count of each word in
words. - For each starting point, check if the words in the current window match the frequency count.
- Use a dictionary to store the frequency count of each word in
- Validation:
- For each window, split the substring into words of
word_lenand check if these words match the frequency count ofwords.
- For each window, split the substring into words of
Python
from typing import List
from collections import Counter
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
word_len = len(words[0])
num_words = len(words)
concat_len = word_len * num_words
s_len = len(s)
if s_len < concat_len:
return []
# Create a frequency count of the words
word_count = Counter(words)
result = []
# Traverse through the string with a sliding window of size concat_len
for i in range(s_len - concat_len + 1):
# Extract the current window
window = s[i:i + concat_len]
# Create a frequency count of the words in the current window
seen_words = []
for j in range(0, concat_len, word_len):
current_word = window[j:j + word_len]
seen_words.append(current_word)
seen_word_count = Counter(seen_words)
# Check if the current window's word frequency matches the target word frequency
if seen_word_count == word_count:
result.append(i)
return resultSolution in Javascript:
JavaScript
/**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
var findSubstring = function(s, words) {
if (s.length === 0 || words.length === 0) return [];
const wordLen = words[0].length;
const numWords = words.length;
const concatLen = wordLen * numWords;
const sLen = s.length;
if (sLen < concatLen) return [];
// Create a frequency map of the words
const wordCount = {};
for (const word of words) {
if (wordCount[word] == null) wordCount[word] = 0;
wordCount[word]++;
}
const result = [];
// Traverse through the string with a sliding window of size concatLen
for (let i = 0; i <= sLen - concatLen; i++) {
const window = s.substring(i, i + concatLen);
// Create a frequency map of the words in the current window
const seenWords = {};
let j = 0;
while (j < concatLen) {
const currentWord = window.substring(j, j + wordLen);
if (wordCount[currentWord] == null) break;
if (seenWords[currentWord] == null) seenWords[currentWord] = 0;
seenWords[currentWord]++;
if (seenWords[currentWord] > wordCount[currentWord]) break;
j += wordLen;
}
// If we processed the entire window, check if seenWords matches wordCount
if (j === concatLen) result.push(i);
}
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (s == null || s.length() == 0 || words == null || words.length == 0) {
return result;
}
int wordLen = words[0].length();
int numWords = words.length;
int concatLen = wordLen * numWords;
int sLen = s.length();
if (sLen < concatLen) {
return result;
}
// Create a frequency map of the words
Map<String, Integer> wordCount = new HashMap<>();
for (String word : words) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
// Iterate with multiple starting points
for (int i = 0; i < wordLen; i++) {
int left = i;
int right = i;
int count = 0;
Map<String, Integer> seenWords = new HashMap<>();
while (right + wordLen <= sLen) {
String word = s.substring(right, right + wordLen);
right += wordLen;
if (wordCount.containsKey(word)) {
seenWords.put(word, seenWords.getOrDefault(word, 0) + 1);
count++;
while (seenWords.get(word) > wordCount.get(word)) {
String leftWord = s.substring(left, left + wordLen);
seenWords.put(leftWord, seenWords.get(leftWord) - 1);
count--;
left += wordLen;
}
if (count == numWords) {
result.add(left);
}
} else {
seenWords.clear();
count = 0;
left = right;
}
}
}
return result;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<int> FindSubstring(string s, string[] words) {
List<int> result = new List<int>();
if (s == null || s.Length == 0 || words == null || words.Length == 0) {
return result;
}
int wordLen = words[0].Length;
int numWords = words.Length;
int concatLen = wordLen * numWords;
int sLen = s.Length;
if (sLen < concatLen) {
return result;
}
// Create a frequency map of the words
Dictionary<string, int> wordCount = new Dictionary<string, int>();
foreach (var word in words) {
if (wordCount.ContainsKey(word)) {
wordCount[word]++;
} else {
wordCount[word] = 1;
}
}
// Iterate with multiple starting points
for (int i = 0; i < wordLen; i++) {
int left = i;
int right = i;
int count = 0;
Dictionary<string, int> seenWords = new Dictionary<string, int>();
while (right + wordLen <= sLen) {
string word = s.Substring(right, wordLen);
right += wordLen;
if (wordCount.ContainsKey(word)) {
if (seenWords.ContainsKey(word)) {
seenWords[word]++;
} else {
seenWords[word] = 1;
}
count++;
while (seenWords[word] > wordCount[word]) {
string leftWord = s.Substring(left, wordLen);
seenWords[leftWord]--;
if (seenWords[leftWord] == 0) {
seenWords.Remove(leftWord);
}
count--;
left += wordLen;
}
if (count == numWords) {
result.Add(left);
}
} else {
seenWords.Clear();
count = 0;
left = right;
}
}
}
return result;
}
}