Sliding Window 9 - Hard - Substring with Concatenation of All Words - JAVA
Coding Interviews - Substring with Concatenation of All Words (LeetCode)
This interview question is commonly asked by companies like Apple, Amazon.
It has a lot of similarities with 'Max Sum Subarray of Size K'. We will use Sliding Window approach + HashMap to capture the frequencies of the words in string array , along with example.
Time Complexity -
The time complexity of the above algorithm will be O(N * M * Len), where ‘N’ is the number of characters in the given string, ‘M’ is the total number of words, and ‘Len’ is the length of a word.
Space Complexity -
The space complexity of the algorithm is O(M) since at most, we will be storing all the words in the two HashMaps. In the worst case, we also need O(N) space for the resulting list. So, the overall space complexity of the algorithm will be O(M+N).
Link to the videos of Sliding Window playlist
1. Max sum subarray of size k - • Sliding Window 1- Easy...
2. Smallest Subarray with a given sum / Minimum Size Subarray Sum - • Sliding Window 2- Easy...
3. Longest Substring with K Distinct Characters - • Sliding Window 3 - Med...
4. Longest Substring with distinct (without repeating) Characters - • Sliding Window 4 - Med...
5. Longest Substring with same letters after replacement - • Sliding Window 5 - Med...
6. Permutation in a String - • Sliding Window 6 - Med...
7. String Anagrams - • Sliding Window 7 - Med...
8. Minimum window substring - • Sliding Window 8 - Har...
9. Words Concatenation - • Sliding Window 9 - Har...
Know more about me
LinkedIn - / umang-mavani
Пікірлер: 16
best explanation I've seen, thank you!
@umangmavani7594
5 ай бұрын
Glad it helped you. Thank you
Neat explanation!
This is a superior explanation. I appreciate it. One thing: The video is slightly sped up
@umangmavani7594
Жыл бұрын
Glad you liked it. Thank you for letting me know, will take care in next videos 👍
wonderful explanation...just keep it going...
@umangmavani7594
Жыл бұрын
Thank you, I will
Awesome explanation
@umangmavani7594
Жыл бұрын
Glad you liked it
Quite helpful !! but you can go bit slow while explaining just a suggestion :)
Nice Explanation 1 doubt T.C should be N*M right? Length of word does not matter I think can you please tell why length is considered Out side loop at max will run N-small value and inner loop will at max M times
@umangmavani7594
Жыл бұрын
Thank you, hope this helped you. The wordLength will be a part of TC because it is getting used in 'j' loop in substring to set our nextWord which is acting as our sliding window.
if wordscount is 2. then i=0 to i
@chiragjain1424
Жыл бұрын
same doubt
@umangmavani7594
Жыл бұрын
You mean the inner 'j' loop ? If yes, below is the reason That loop is used to keep the track of nextIndex of the word to be used in substring and not to traverse the wordCount, see from 7:00 If j
class Solution { public List findSubstring(String s, String[] words) { Map map = new HashMap(); for(String word: words){ map.put(word, map.getOrDefault(word, 0) + 1); } List result = new ArrayList(); int wordsCount = words.length; int wordLength = words[0].length(); for(int i = 0; i map.getOrDefault(nextWord, 0)) break; if(j + 1 == wordsCount) result.add(i); } } return result; } }