longest repeating common substring can be on various types . One which I am talking about is like :-
- Substring- A string a is a substring of a string S if a can be obtained from S by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
- Longest Repeating — The string has longest repeating substring when it has longest length among all possible fellow substrings of its parent string.
This is an important concept to learn as it is useful in many questions : [problem:101262/B]
[problem:1584/F]
[problem:[problem:1948/D] [submission:253170793]]
Approach In these kinds of problem you need to think you reusing previous values to take desicion based on them. Think of a Dynamic Programming always in such cases. . Some question might take recursion so you can optimize them with memoization.
Complexity with DP Time : O(n^2) Space : O(n^2) (depending upon size of data structure and variables used).
Additional Resources Practice problem based on LCS
