You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated substring in s is a substring that 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 substring because it is not the concatenation of any permutation ofwords.
Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6. 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. The output order does not matter. Returning [9,0] is fine too.
Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: [] Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16. There is no substring of length 16 is s that is equal to the concatenation of any permutation of words. We return an empty array.
Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] Output: [6,9,12] Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9. The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words. The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words. The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.
Constraints:
1 <= s.length <= 1041 <= words.length <= 50001 <= words[i].length <= 30sandwords[i]consist of lowercase English letters.
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
cnt = Counter(words)
sublen = len(words[0])
n, m = len(s), len(words)
ans = []
for i in range(sublen):
cnt1 = Counter()
l = r = i
t = 0
while r + sublen <= n:
w = s[r : r + sublen]
r += sublen
if w not in cnt:
l = r
cnt1.clear()
t = 0
continue
cnt1[w] += 1
t += 1
while cnt1[w] > cnt[w]:
remove = s[l : l + sublen]
l += sublen
cnt1[remove] -= 1
t -= 1
if m == t:
ans.append(l)
return ansclass Solution {
public List<Integer> findSubstring(String s, String[] words) {
Map<String, Integer> cnt = new HashMap<>();
for (String w : words) {
cnt.put(w, cnt.getOrDefault(w, 0) + 1);
}
int subLen = words[0].length();
int n = s.length(), m = words.length;
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < subLen; ++i) {
Map<String, Integer> cnt1 = new HashMap<>();
int l = i, r = i;
int t = 0;
while (r + subLen <= n) {
String w = s.substring(r, r + subLen);
r += subLen;
if (!cnt.containsKey(w)) {
l = r;
cnt1.clear();
t = 0;
continue;
}
cnt1.put(w, cnt1.getOrDefault(w, 0) + 1);
++t;
while (cnt1.get(w) > cnt.get(w)) {
String remove = s.substring(l, l + subLen);
l += subLen;
cnt1.put(remove, cnt1.get(remove) - 1);
--t;
}
if (m == t) {
ans.add(l);
}
}
}
return ans;
}
}class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> cnt;
for (auto& w : words) cnt[w]++;
int subLen = words[0].size();
int n = s.size(), m = words.size();
vector<int> ans;
for (int i = 0; i < subLen; ++i) {
unordered_map<string, int> cnt1;
int l = i, r = i;
int t = 0;
while (r + subLen <= n) {
string w = s.substr(r, subLen);
r += subLen;
if (!cnt.count(w)) {
l = r;
t = 0;
cnt1.clear();
continue;
}
cnt1[w]++;
t++;
while (cnt1[w] > cnt[w]) {
string remove = s.substr(l, subLen);
l += subLen;
cnt1[remove]--;
--t;
}
if (t == m) ans.push_back(l);
}
}
return ans;
}
};class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> d;
for (auto& w : words) ++d[w];
vector<int> ans;
int n = s.size(), m = words.size(), k = words[0].size();
for (int i = 0; i < k; ++i) {
int cnt = 0;
unordered_map<string, int> t;
for (int j = i; j <= n; j += k) {
if (j - i >= m * k) {
auto s1 = s.substr(j - m * k, k);
--t[s1];
cnt -= d[s1] > t[s1];
}
auto s2 = s.substr(j, k);
++t[s2];
cnt += d[s2] >= t[s2];
if (cnt == m) ans.emplace_back(j - (m - 1) * k);
}
}
return ans;
}
};func findSubstring(s string, words []string) []int {
cnt := map[string]int{}
for _, w := range words {
cnt[w]++
}
subLen := len(words[0])
n, m := len(s), len(words)
var ans []int
for i := 0; i < subLen; i++ {
cnt1 := map[string]int{}
l, r := i, i
t := 0
for r+subLen <= n {
w := s[r : r+subLen]
r += subLen
if _, ok := cnt[w]; !ok {
l = r
t = 0
cnt1 = map[string]int{}
continue
}
cnt1[w]++
t++
for cnt1[w] > cnt[w] {
remove := s[l : l+subLen]
l += subLen
cnt1[remove]--
t--
}
if t == m {
ans = append(ans, l)
}
}
}
return ans
}public class Solution {
public IList<int> FindSubstring(string s, string[] words) {
var wordsDict = new Dictionary<string, int>();
foreach (var word in words)
{
if (!wordsDict.ContainsKey(word))
{
wordsDict.Add(word, 1);
}
else
{
++wordsDict[word];
}
}
var wordOfS = new string[s.Length];
var wordLength = words[0].Length;
var wordCount = words.Length;
for (var i = 0; i <= s.Length - wordLength; ++i)
{
var substring = s.Substring(i, wordLength);
if (wordsDict.ContainsKey(substring))
{
wordOfS[i] = substring;
}
}
var result = new List<int>();
for (var i = 0; i <= s.Length - wordLength * wordCount; ++i)
{
var tempDict = new Dictionary<string, int>(wordsDict);
var tempCount = 0;
for (var j = i; j <= i + wordLength * (wordCount - 1); j += wordLength)
{
if (wordOfS[j] != null && tempDict[wordOfS[j]] > 0)
{
--tempDict[wordOfS[j]];
++tempCount;
}
else
{
break;
}
}
if (tempCount == wordCount)
{
result.Add(i);
}
}
return result;
}
}