Longest Duplicate Substring | TRIE | Rolling Hash | Binary Search | Leetcode

This video explains a very important programming interview problem which is to find the longest duplicate substring in the given string.There are many ways to solve this problem.I have explained 3 methods to solve this problem.The first method is by using dynamic programming because this problem is a variant of LCS or longest common substring.DP fails because we can't make a large table.The second approach is to solve it using TRIE.In this approach, we keep inserting all substrings of given size and whenever during insertion in our trie, we finnd that the substring is already present then that must be a common substring.We apply binary search on length of substring to find the maximum length for which there are two duplicate substrings.The third approach is by using rolling hash, binary search and hashmap.This is making use of rabin karp algorithm.This is the fastest among the 3 methods explained.The fastest method to solve this problem is by using Ukkonen's suffix tree, which solves this problem in two steps in just O(N) time.I have explained all the methods with intuition and proper examples.I have also shown the code walk through at the end of the video.

CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

=================================================================
INSTAGRAM:   / surya.pratap.k  
LinkedIn:   / surya-pratap-kahar-47bb01168  
=================================================================

CODE LINK: https://gist.github.com/SuryaPratapK/...
USEFUL LINKS:-
Longest Common Substring (LCS):    • Longest common substring | Dynamic program...  

Basics of trie:    • Basics of trie  
TRIE Insertion & Search:    • Trie insertion and search  
TRIE Deletion & Search:    • Trie deletion and search  
Rolling Hash (Rabin Karp algo):    • Rolling hash | Rabin karp algorithm | Patt...