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 in s that is equal to the concatenation of any permutation of words. We return an empty array.
Constraints:
1 <= s.length <= 1041 <= words.length <= 50001 <= words[i].length <= 30sandwords[i]consist of lowercase English letters.
Solution
class Solution {
public:
struct matcher {
struct info { int mtindex, count; };
unordered_map<string_view, info>dict;
int different_word_count;
vector<int>slot;
int maching_slot_count;
matcher(const vector<string>& words) {
int mtind = 0;
for (auto& word : words) {
auto find = dict.find(word);
if (find != dict.end()) {
++find->second.count;
}
else { dict[word] = { mtind++,1 }; }
}
different_word_count = mtind;
slot = vector<int>(different_word_count, 0);
maching_slot_count = 0;
}
void reset() {
for (auto& i : slot) { i = 0; }
maching_slot_count = 0;
}
bool match() {
return maching_slot_count == different_word_count;
}
void push(string_view sv) {
auto find = dict.find(sv);
if (find == dict.end())return;
if (++slot[find->second.mtindex] == find->second.count) {
++maching_slot_count;
}
}
void pop(string_view sv) {
auto find = dict.find(sv);
if (find == dict.end())return;
if (--slot[find->second.mtindex] == find->second.count - 1) {
--maching_slot_count;
}
}
};
vector<int> findSubstring(string s, const vector<string>& words) {
int word_count = words.size();
int word_len = words[0].size();
matcher matcher(words);
const char* str = s.c_str();
int len = s.size();
vector<int> ret;
for (int off = 0; off < word_len; off++) {
const char* beg = str + off, * end = str + len;
if (beg + word_len * word_count <= end) {
matcher.reset();
for (int i = 0; i < word_count; i++) {
string_view sv(beg + i * word_len, word_len);
matcher.push(sv);
}
if (matcher.match()) {
ret.push_back(beg - str);
}
const char* pos = beg + word_len * word_count;
while (pos + word_len <= end) {
string_view del(beg, word_len);
string_view add(pos, word_len);
beg += word_len;
pos += word_len;
matcher.pop(del);
matcher.push(add);
if (matcher.match()) {
ret.push_back(beg - str);
}
}
}
}
return ret;
}
};class Solution {
public List<Integer> findSubstring(String s, String[] words) {
int wordLength = words[0].length();
int totalWordsLength = wordLength * words.length;
Map<String, Integer> hash = new HashMap<>();
List<Integer> ans = new ArrayList<>();
char[] s2 = s.toCharArray();
for (String value : words) {
hash.putIfAbsent(value, hash.size());
}
int[] count = new int[hash.size()];
for (String word : words) {
count[hash.get(word)]++;
}
for (int i = 0; i < wordLength; i++) {
for (int j = i; j <= s.length() - totalWordsLength; j += wordLength) {
int[] localCount = new int[hash.size()];
for (int k = j + totalWordsLength - wordLength; k >= j; k -= wordLength) {
String str = new String(s2, k, wordLength); // [ k, k+wordLength )
Integer key = hash.get(str);
if (!(key != null && count[key] >= ++localCount[key])) {
j = k;
break;
}
if (j == k) {
ans.add(j);
}
}
}
}
return ans;
}
}class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
n_word = len(words)
n_char = len(words[0])
word2freq = {}
for word in words:
if word in word2freq:
word2freq[word] += 1
else:
word2freq[word] = 1
all_start_ind = []
for start_ind in range(n_char):
curr_map = {}
curr_total = 0
excessive = False
for i in range(start_ind, len(s), n_char):
word = s[i:i+n_char]
if word in word2freq: # a valid word for permutation
curr_total += 1
if word in curr_map: # found valid word
curr_map[word] += 1
if curr_map[word] > word2freq[word]:
excessive = word
else:
curr_map[word] = 1
earliest_ind = i - (curr_total-1)*n_char
while excessive:
earliest_word = s[earliest_ind: earliest_ind+n_char]
curr_map[earliest_word] -= 1
curr_total -= 1
if earliest_word == excessive:
excessive = False
break
earliest_ind += n_char
if curr_total == n_word:
earliest_ind = i - (n_word-1)*n_char
all_start_ind.append(earliest_ind)
earliest_word = s[earliest_ind: earliest_ind+n_char]
curr_total -= 1
curr_map[earliest_word] -= 1
else:
curr_total = 0
curr_map = {}
return all_start_ind
def check_map_equal(self, curr_map, ref_map) -> bool:
for word, freq in curr_map.items():
if word not in ref_map or freq != ref_map[word]:
return False
return TrueHappy Learning – If you require any further information, feel free to contact me.
![[Solved] Minimum Score After Removals on a Tree LeetCode Contest Problem](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-Minimum-Score-After-Removals-on-a-Tree-LeetCode-Contest-Problem-300x200.png)
![[Solved] Match Substring After Replacement LeetCode Contest Problem](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-Match-Substring-After-Replacement-LeetCode-Contest-Problem-300x200.png)