Substring with Concatenation of All Words | Leetcode #30

This video explains about finding all the substrings with any valid combination of words that can be formed. This is from leetcode 30 and is based on sliding window on string.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone]
---------------------------------------------------------------------------------------------------------------------------------------------------------------

[prashantbharti]

One way to optimize this implementation is to store all already checked substrings in input S against there evaluation output matched/not matched. If the same substring comes up again later for matching then we can avoid processing it on the basis of the stored matched/not matched value. If matched then current substring will also match. If not matched then current will not match. It will help us bypass the testcase of S = of length 10000 and words = {"a", "a", ... "a"} of length = 5000. It will increase memory usage but help to optimize on latency.

[Nikhil_Shubham]

to be honest, explanation can be improved.

[MrLeyt]

Great vid, but leetcode wont accept it
Time Limit Exceeded
179 / 179 testcases passed
Testcases passed, but took too long.

[harsha]

java code
explained the same way , not my sol
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ans = new ArrayList<>();
int n = s.length();
int m = words.length;
int w = words[0].length();

HashMap<String, Integer> map = new HashMap<>();
for(String x : words)
map.put(x, map.getOrDefault(x, 0)+1);

for(int i=0; i<w; i++){
HashMap<String, Integer> temp = new HashMap<>();
int count = 0;
for(int j=i, k=i; j+w <= n; j=j+w){
String word = s.substring(j, j+w);
temp.put(word, temp.getOrDefault(word, 0)+1);
count++;

if(count==m){
if(map.equals(temp)){
ans.add(k);
}
String remove = s.substring(k, k+w);
temp.computeIfPresent(remove, (a, b) -> (b > 1) ? b - 1 : null);
count--;
k=k+w;
}
}//inner for loop
}//outer for loop
return ans;
}//method
}//class

[ahyungrocks]

At time 9min 4s, I am still not able to comprehend why you don't need to process every position. Appreciate it if you can elaborate more.

[vishalgadade]

Left shift is missing that's why 0ne test case is missing..

[madhavilathakarumanchi]

Sorry to say this, Little tricky to understand the explanation you have given.