• 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

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave