3292. Minimum Number of Valid Strings to Form Target II | Weekly Leetcode 415 | Z-Algorithm

[@miketsubasa3611]

Superb Explanation as always.These days I look for your explanation videos in every leetcode contest 4th problems

[@DachuanHuang]

good explanation, good pace.

[@Yadavprash9]

Thanks, really appreciate the video, though I am just starting to learn these concepts, the thought process was good to know, going to checkout the playlists in the description :)

[@nikhilsoni2403]

Great explaination ❤. The z function approach is really understandable .

[@ziqyeow]

bro, I've subscribed, keep doing what you are doing, your channel is literally underrated.

[@sonugupta147]

Your explanation is really impressive. The ideas and observations you put at every step.. its just the evidence of how a problem should be approached.

[@nikhilprakash729]

Great Solution...

[@SaquibAnsariofficial01]

Can you explain about the seg tree why minimum?

[@jaiyantjakhar5635]

you earned a subscriber today, great great work preparing for uber, want to give any tips, suggestions

[@jaiyantjakhar5635]

also if we use hash as: ap^3 + bp^2 + cp + d (for string "abcd" and base p) then we don't have to use inverse powers doesn't mean much but skips inverse modulo use

[@NikhilTiwari-to7sv]

we can also precompute a rolling hash using rabin karp algorithm instead of building trie time complexity will remain the same..

[@codingmohan]

Yes that would work too.

[@codeyourideas]

getting tle with the approach of 3 problem using recursion + memo+trie, please look into my solution

[@codingmohan]

Hope this is resolved now?

[@Cools74]

Please try to upload yesterday biweekly contest 3rd problem 🙏

[@codingmohan]

Here you go - kzbin.info/www/bejne/m5KcfJ2cmJ6NsKs

[@Cools74]

@@codingmohan Thanks a lot 😭

[@priyanshupriyadarshi502]

Hi Bro, really good content. intuition is clear. I first tried submitting my code similar to yours 1st approach( using hashing ) but got wrong answer at 799/807. After that I submitted your code and faced the same issue. can you pls look into this.

[@codingmohan]

They might have updated the test case to introduce collision for the specific hash function we are using. You can just duplicate the hash calculation with different values of P and/or MOD and compare as a pair instead of single value to avoid collision.

[@codingmohan]

To be honest, if you are able to reach 799 test cases through your code, you probably understand everything that this approach would teach you and simply move forward to different approach :)

[@codeyourideas]

Still getting TLE. 916/929 :((((

[@codingmohan]

Replied to the other comment. Let me know if you are still facing issues.

[@codeyourideas]

class Solution { HashMap map=new HashMap(); class TrieNode { TrieNode[] children; boolean isEndOfWord; public TrieNode() { children = new TrieNode[26]; isEndOfWord = false; } } public void insert(String word, TrieNode root) { TrieNode node = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { node.children[index] = new TrieNode(); } node = node.children[index]; } node.isEndOfWord = true; } public boolean findWordsWithPrefix(String prefix, TrieNode root) { TrieNode node = root; int result=0; for (char c : prefix.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { return false; // No match for the prefix } else result++; node = node.children[index]; } return true; } public int find(String s, TrieNode root, HashMap memo, int index, int n){ // System.out.println(s); // int n1=s.length(); if(index==n) return 0; if(memo.containsKey(index)) return memo.get(index); boolean found=false; int x=10000000; String temp=""; for(int i=index;i

[@codingmohan]

if(map.containsKey(temp)) cnt=map.get(temp); else { cnt=findWordsWithPrefix(temp, root); map.put(temp, cnt); } Why are you creating a temporary string and the searching it in a hashmap. Why not simply iterate over the trie and let trie do the work? Something like - tmp_root = root for(int i=index;i

[@ujjwalagnihotri5001]

Java's HashMap is too slow, apart from above optimization use array for dp and trie.

[@codeyourideas]

@@codingmohan thanks, i got u.