After your explanation i realised why in the problem words have same length. Thank you so much for the wonderful explanation. Best wishes. Keep it up :)
Great explanation. I think you should also relate these problems to the design pattern that is used to help students identify which pattern to use for each problem. For example, this one is sliding window. This would help to simplify coding interview problems.
Instead of 2 for-loops; backtracking can also work: public List findSubstring(String s, String[] words) { final Map freqMap = new HashMap(); for (final String word : words) { freqMap.put(word, freqMap.getOrDefault(word, 0) + 1); } final int wordCount = freqMap.size(); final int wordLen = words[0].length(); final Map currFreq = new HashMap(); final Map lastPos = new HashMap(); final List result = new ArrayList(); for (int i = 0; i < s.length() - wordLen + 1;) { final String sub = s.substring(i, i + wordLen); if (freqMap.containsKey(sub)) { currFreq.put(sub, currFreq.getOrDefault(sub, 0) + 1); lastPos.putIfAbsent(sub, i); final int maxFreq = freqMap.get(sub); final int freq = currFreq.get(sub); if (freq > maxFreq) { i = lastPos.get(sub) + 1; lastPos.clear(); currFreq.clear(); } else if (freqMap.equals(currFreq)) { final int minPos = Collections.min(lastPos.values()); result.add(minPos); i = minPos + 1; lastPos.clear(); currFreq.clear(); } else { i += wordLen; } } else { if (!currFreq.isEmpty()) { i = Collections.min(lastPos.values()) + 1; } else { i++; } lastPos.clear(); currFreq.clear(); } } return result; }
Nice explanation sir, Thank you !
After your explanation i realised why in the problem words have same length.
Thank you so much for the wonderful explanation.
Best wishes.
Keep it up
:)
Thanks for your nice feedback. Keep Watching.
Great explanation. I think you should also relate these problems to the design pattern that is used to help students identify which pattern to use for each problem. For example, this one is sliding window. This would help to simplify coding interview problems.
Thanks for your nice feedback. Sure, I'll try to add in my upcoming videos.
@@CodingSimplified Thanks. Your videos are great and a great help.
Instead of 2 for-loops; backtracking can also work:
public List findSubstring(String s, String[] words) {
final Map freqMap = new HashMap();
for (final String word : words) {
freqMap.put(word, freqMap.getOrDefault(word, 0) + 1);
}
final int wordCount = freqMap.size();
final int wordLen = words[0].length();
final Map currFreq = new HashMap();
final Map lastPos = new HashMap();
final List result = new ArrayList();
for (int i = 0; i < s.length() - wordLen + 1;) {
final String sub = s.substring(i, i + wordLen);
if (freqMap.containsKey(sub)) {
currFreq.put(sub, currFreq.getOrDefault(sub, 0) + 1);
lastPos.putIfAbsent(sub, i);
final int maxFreq = freqMap.get(sub);
final int freq = currFreq.get(sub);
if (freq > maxFreq) {
i = lastPos.get(sub) + 1;
lastPos.clear();
currFreq.clear();
} else if (freqMap.equals(currFreq)) {
final int minPos = Collections.min(lastPos.values());
result.add(minPos);
i = minPos + 1;
lastPos.clear();
currFreq.clear();
} else {
i += wordLen;
}
} else {
if (!currFreq.isEmpty()) {
i = Collections.min(lastPos.values()) + 1;
} else {
i++;
}
lastPos.clear();
currFreq.clear();
}
}
return result;
}
Well explained it made my understanding clear!
Thanks for your feedback. Keep Watching.
Such an elegant explanation. Thank you for this.
Thanks for your nice feedback. Keep Watching.
Awesome Explanation man...
hard question but your explanation is really outstanding
Thanks for your nice feedback. Keep watching.
Really an amazing explanation.
Thankyou for the explanation
Explained awesome!
Thank you sir
Thanks for your nice feedback. Keep Watching.
Amazing explanation
Great experience
Thanks Purav for your feedback. Keep Watching.
Time complexity O(n * m * length), please correct the description
Thanks for notifying. Looks like I missed updating in Description. Updated now.
Shouldn't be it getting TLE..
n=3*10^4
m=5000
length=30
O(4.5*10^9)
@@jitendranagar8962 nAH, the reason being he's using early pruning, hence as soon as there is a mismatch, he breaks out. BUT YEAH. WORST CASE CAN TLE
Awesome :)
Thanks for your nice feedback. Keep watching.
what is the difference bwteen str==null and str.length()==0?
Empty string is not null. String with length 0 is “”
great explaination, but I hope I don't get this in my interview
Yeah, I can understand it. Tough question it is :) BTW thanks for your nice feedback.
If they ask this in interview, try this .
class Solution {
public List findSubstring(String s, String[] words) {
HashMap given = new HashMap();
HashMap formed = new HashMap();
for(String word : words)
given.put(word,given.getOrDefault(word,0)+1);
List result = new ArrayList();
int wordLength = words[0].length();
for(int end=0;end
You lost me at concanet