Interview Question: String Deletion

[@carteryu967]

Probably one of the most underrated channels on YT. I've been going through a lot of your vids lately. You rock dude please keep it up! :)

[@ByteByByte]

Thank you so much! I really appreciate the kind words

[@mukundsridhar4250]

Excellent work sam....did you mean String s1 = s.subString(0,i) ; String s2 = s.subString(i+1,s,.length())) and then mean to add s1 and s2 into the queue. Here you are concatenation s1 and s2 which again gives "s". Thank you once again for all your excellent work.

[@biswamohandwari6460]

You are a very good teacher 😊

[@rkb78678]

awesome explaination...one of the best channel to learn. a question though, will it do any harm if we don't remove from queueElement set? it's like a visited set in bfs

[@waterislife9]

Yepp, there's no harm; we can just have a `visited = {}` and throw all the checked string values in the hash

[@BlitzDjingga]

At the beginning you are giving example of “aaa” changed to “abc” by replacing two characters.. On the problem statement it is asking for number of characters to delete to make word.. Your solution is about what minimal characters i have in dictionary that match subset of characters in query.. 🤯☠️🤯 Am we not supposed to get all permutation of words in dictionary with the same length first, than from there which word has the minimum deletions?

[@IoTLearner]

My first approach on seeing this problem :) int charToDelete(String query, Set set ) { StringBuilder str=new StringBuilder(query.charAt(0)); int c=0; for(int i=0;i

[@swetha8915]

Hi Sam, Great explanation! Thank you for your videos :) In this question, why do we need a queueElements set? Why can't we just use a queue and output the result when a match is found? (Since we are already following BFS and can be certain of best to worst outputs of strings). Also, since we are only required to return the number of characters to be deleted, we might not need to keep track of visited nodes using queueSet. We can check for the presence of the substring in the queue before adding to avoid duplicates. Please let me know if I'm missing something here. Thank you. def stringDeletion(s, d): queue=[] queue.append(s) while queue: curr = queue.pop(0) if curr in d: return curr, len(s)-len(curr) for ind in range(len(curr)): sub = curr[0:ind]+curr[ind+1:] if len(sub) and sub not in queue>0: queue.append(sub) return None print(stringDeletion('abc', ['a', 'aa', 'aaa']))

[@waterislife9]

I think your implementation is fine. Using a mirror set might be better if we're optimizing for time. Hash lookup will be O(1) while checking for an item in items queue will take O(m) where m is length of queue

[@swetha8915]

@@waterislife9 Thank you @dm. I missed the time complexity part :)

[@svenjaaunes2507]

if you dynamic programming for each element in the dictionary against the query, will we get O(n*2^n) because we wont benefit from the dictionary being a hashset ? basically will this dp (between an element in the dictionary and the query) run in O(2^n)? dp=edit distance with only deletion operation

[@shivampatel8928]

Great explanation... Just loved it. One recommendation is to use some drawing tool to explain the problem and its approach.. Instead the text editor. Rest it was so so awesome.

[@ByteByByte]

Thanks! And you're not the first person to make that suggestion. I've been looking into getting some sort of tablet to do just that

[@xiaoyu88]

if there's anyone here with c# and cant understand the line suffix.substring(i+1,suffix.length()), you need to translate it to suffix.substring(i+1,suffix.length() - i -1) so you wont be out of range.

[@pradipnitw]

after the optimisation isn't the run time be bound to O(2^n)? because the number of substring of a string is bound by (present/not-present)^n Since factorial outgrows exponential functions for larger values of N, this would be what we desire.

[@ByteByByte]

We're really looking at subsequences, not substrings

[@Achilleus003]

Awesome explanation!! Thank you so much and I really appreciate all your efforts . But yeah a drawing tool would really make your videos even more awesome!! Cheers..

[@GoldenReviewer]

is Linked HashSet a good data structure for this problem?

[@ByteByByte]

How would you use that in your solution?

[@GoldenReviewer]

In your solution you maintain a LinkedList and a HashSet separately, to achieve O(1) lookup and O(1) enqueue/dequeue. I suppose the same can be achieved with LinkedHashSet? I know that LinkedHashSet does not implement Queue interface, but maybe we can use iterator to remove the oldest element(dequeue), and add() method to add to the end of the list(enqueue), they should also take O(1) time?

[@ByteByByte]

Ah yeah that makes sense. I don't know much about LinkedHashSets, but if it has all the necessary properties, that seems like a very reasonable way to do it

[@MrMikomi]

I was thinking the same even though I don't understand his solution

[@ericacm]

Here's a backtracking-based solution. Interesting that you can look at backtracking and BFS as similar: def min_deletions_in_dictionary(dictionary, s): def backtrack(k, remaining): if not s: return -1 elif remaining in dictionary: return k else: candidates = {remaining[:i] + remaining[i+1:] for i in range(len(remaining))} for rem in candidates: res = backtrack(k + 1, rem) if res != -1: return res return -1 return backtrack(0, s)

[@theofficialbooya]

How will it affect the solution if you would've known the strings in the dictionary?

[@jakegarza4548]

My guess would be that you could create a trie with the dictionary of possible strings. From there you could iterate over the trie and check whether it's possible to change the query to fit the current trie node. Not sure if this is more efficient though

[@gswathi9225]

Can we use Trie for solving this problem?

[@HarishAmarnath]

I was thinking the same.. TRIE is good option

[@ItachiXSanjii]

@@HarishAmarnath but you don't know about the all Strings in dictionary. Only you can check if any string is there or not. So can't create a Trie if you don't know all the strings.

[@svenjaaunes2507]

i think you should not rekove queueElements.remove() because if you get 2 instances of the same substring in tue queue, after the first one is removed, the second will be processes again unnecessarily since queueElements wont contain it because it is removed from the queue elements after the first instance in the queue is removed

[@anvesh687]

I thought so too initially, but as we are processing each level separately(bfs), so at every level, we restrict adding duplicates and remove after that, because the next level would only have strings with one less character. Hope this makes sense to you.

[@debagnikroy9450]

@@anvesh687 yeah you ar right! nice observation bro :D So basically since its not possible to have same string at two different levels, thats y we are removing it.... so actually if we write/dont write the remove statement, the answer would stay the same...right?

[@anvesh687]

@@debagnikroy9450 Yeah, I guess we gain performance in the first approach. Hence, efficient code

[@debagnikroy9450]

@@anvesh687 yeah right... performance is better i guess

[@nagarjuna119]

very good but font too small..

[@ByteByByte]

Nagarjuna Y thanks! And yeah I know I've been trying to keep it larger in more recent videos

[@tushargoel5522]

you have considered only 'ab' as a pair but 'ba' could also be possible..

[@9738803535]

The substring taking code is not convincing

[@roberthelk6492]

DFS might be viable option especially if going for space. For optimization might have current answer as parameter for recursion. I.E. 0 at start until finds substring and then in future searches uses that length to make sure never goes deeper.

[@ByteByByte]

Yeah that could work