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

Similar Hashing Problems -

*************************************************

*************************************************
Timestamps -

00:00 - Agenda
00:27 - Problem Description
02:50 - [Brute Force] Intuition of recursion
05:08 - [Brute Force] Dry run of Algorithm
10:20 - [Brute Force] Pseudo code & Time Complexity
17:40 - [Optimisation 1] Intuition + Dry run
21:20 - [Optimisation 1] Pseudo code & Time Complexity
23:06 - [Optimisation 2] Intuition
25:55 - [Optimisation 2] Using range query with bottom-up
29:45 - [Optimisation 2] Optimising the matching function
36:25 - [Optimisation 2] Code Walkthrough
41:46 - [Optimisation 3] Intuition + Dry run
46:50 - [Optimisation 3] Time Complexity
48:38 - [Optimisation 3] Code Walkthrough

*************************************************
Interview Experiences Playlists -

*********************************************************************

Please show support and subscribe if you find the content useful.

[miketsubasa]

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

[nikhilsoni]

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.

[sonugupta]

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.

[Yadavprash]

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 :)

[jaiyantjakhar]

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

[NikhilTiwari-tosv]

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

[Cools]

Please try to upload yesterday biweekly contest 3rd problem 🙏

[priyanshupriyadarshi]

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.

[SaquibAnsariofficial]

Can you explain about the seg tree why minimum?

[codeyourideas]

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

[codeyourideas]

class Solution {
HashMap<String, Boolean> 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<Integer, Integer> 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
String temp="";
for(int i=index;i<s.length();i++){
temp+=s.charAt(i);
boolean cnt=false;
if(map.containsKey(temp))
cnt=map.get(temp);
else {
cnt=findWordsWithPrefix(temp, root);
map.put(temp, cnt);
}
if(cnt) {
// System.out.println(s+" temp: "+temp+" "+" child: ");
int child=find(s, root, memo, i+1, n);

if(child!=-1){
x=Math.min(x, child );
found=true;
}
}
else break;

}
if(!found){
memo.put(index, -1);
return -1;
}
memo.put(index, x+1);
return x+1;
}


public int minValidStrings(String[] words, String target) {
int n=words.length;
TrieNode root=new TrieNode();
for(int i=0;i<n;i++){
insert(words[i], root);
}


HashMap<Integer, Integer> memo=new HashMap<>();
return find(target, root, memo, 0, target.length());

}
}