Longest Repeating Substring
Longest Duplicate Substring

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Problem Statement:
Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists.
Example 1:
Input: S = "abcd"
Output: 0
Explanation: There is no repeating substring.
Example 2:
Input: S = "abbaba"
Output: 2
Explanation: The longest repeating substrings are "ab" and "ba", each of which occurs twice.
Example 3:
Input: S = "aabcaabdaab"
Output: 3
Explanation: The longest repeating substring is "aab", which occurs 3 times.
Example 4:
Input: S = "aaaaa"
Output: 4
Explanation: The longest repeating substring is "aaaa", which occurs twice.
Solution:
This is a problem often asked in coding interviews.
I would highly recommend you gaining a really good good understanding of Advanced Binary Search before solving this problem.
The solution for this chapter is based off of a very simple observation:
if we have a repeating substring of length M, that would also mean
that we have repeating substring of length K, where K < M.
Using this observation,
our problem reduces to finding the substring of longest length that has more than 1 occurrences in the given string.
Using our knowledge gained in of Advanced Binary Search, we can say this problem is all about "
finding the MAXIMUM value in the search space that satisfies certain condition
". In our case,
search space is [0, length of given string] and condition is number of occurrences of the substring >= 2.
We would make certain changes in the template we have discussed in
Advanced Binary Search
to achieve our goal here. Notice that here we are interested in finding
MAXIMUM value in search space in contrast to
Advanced Binary Search
where we were interested in the MINIMUM value in the search space. It is for this reason that we need to do
certain modifications in the
Advanced Binary Search TEMPLATE.
If substring of length mid does not satisfy our condition, no substring of length greater than mid would satisfy the condition either. So we need to search for substring with length less than mid. So we move more towards the left of the search space to access the values lower than mid. We achieve this by contracting our search space appropriately by doing
right = mid;
.
If we get a substring of length mid satisfies our solution, we would look for if there is any other substring of length greater than mid that also satisfies our condition. We achieve this by moving more towards right so that we can access the higher values (values which are greater than mid in the search space) in the search space. We achieve this by contracting search space appropriately by doing
left = mid + 1;
Java Solution with Detailed Explanation of Implementation Logic:
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Python Solution with Detailed Explanation of Implementation Logic:
This is a Premium Content. Please subscribe to access the solution.
After subscribing please come back and refresh this page.
Space Optimization by using Hash Code of Substrings:
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn