Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Substring with Concatenation of All Words LeetCode Solution
Problem – Substring with Concatenation of All Words LeetCode Solution
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.
Substring with Concatenation of All Words LeetCode Solution in Java
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
final Map<String, Integer> counts = new HashMap<>();
for (final String word : words) {
counts.put(word, counts.getOrDefault(word, 0) + 1);
}
final List<Integer> indexes = new ArrayList<>();
final int n = s.length(), num = words.length, len = words[0].length();
for (int i = 0; i < n - num * len + 1; i++) {
final Map<String, Integer> seen = new HashMap<>();
int j = 0;
while (j < num) {
final String word = s.substring(i + j * len, i + (j + 1) * len);
if (counts.containsKey(word)) {
seen.put(word, seen.getOrDefault(word, 0) + 1);
if (seen.get(word) > counts.getOrDefault(word, 0)) {
break;
}
} else {
break;
}
j++;
}
if (j == num) {
indexes.add(i);
}
}
return indexes;
}
}
Substring with Concatenation of All Words LeetCode Solution in Python
from collections import deque, defaultdict
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
word_len = len(words[0])
ori_word_dict = defaultdict(int)
for word in words:
ori_word_dict[word] += 1
all_word_len = len(words) * word_len
result = []
for i in range(word_len):
queue = deque()
word_dict = ori_word_dict.copy()
for j in range(i, len(s) - word_len + 1, word_len):
word = s[j:j + word_len]
if word_dict.get(word, 0) != 0:
word_dict[word] -= 1
queue.append(word)
if sum(word_dict.values()) == 0:
result.append(j - all_word_len + word_len)
last_element = queue.popleft()
word_dict[last_element] = word_dict.get(last_element, 0) + 1
else:
while len(queue):
last_element = queue.popleft()
if last_element == word:
queue.append(word)
break
else:
word_dict[last_element] = word_dict.get(last_element, 0) + 1
if word_dict[last_element] > ori_word_dict[last_element]:
word_dict = ori_word_dict.copy()
return result
Substring with Concatenation of All Words LeetCode Solution in C++
class Solution {
public:
bool checkSubstring(unordered_map<string, int> wordCount, string s, int wordLen) {
for(int j=0; j<s.size(); j+=wordLen) {
string w = s.substr(j, wordLen);
if(wordCount.find(w) != wordCount.end()) {
if(--wordCount[w] == -1) {
return false;
}
} else {
return false;
}
}
return true;
}
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
int wordLen = words[0].size();
int sLen = s.size();
int wordsWindow = words.size() * wordLen;
unordered_map<string, int> wordCount;
for(int i=0; i<words.size(); i++) {
wordCount[words[i]]++;
}
int i = 0;
while(i + wordsWindow <= sLen) {
if(checkSubstring(wordCount, s.substr(i, wordsWindow), wordLen)) {
res.push_back(i);
}
i++;
}
return res;
}
};
Substring with Concatenation of All Words LeetCode Solution Review:
In our experience, we suggest you solve this Substring with Concatenation of All Words LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Substring with Concatenation of All Words LeetCode Solution
Conclusion:
I hope this Substring with Concatenation of All Words LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>
