Longest Repeating and Non-Overlapping Substring in Java
The longest sequence of characters that appears more than once without overlapping, which is called as Longest Repeating and Non-Overlapping substring. The substring cannot have characters that overlap between its occurrences but must occur twice or more. Finding the length of this substring and separating it from the provided input string is the main objective of the longest repeating and non-overlapping substring. Finding the longest substring that appears at least twice in a given input without overlap between its appearances is the objective of the longest repeating and non-overlapping substring issue. Using dynamic programming techniques is one of the efficient ways to overcome the longest repeating and non-overlapping substring. We can find the longest repeating substring by iterating through the string and the usage of a 2D array that stores lengths of common substrings.
Example 1:
Input:
str = "banana"
Output:
an
Explanation:
From the input string "banana", the longest repeating substring is "banana," and the non-overlapping substring will be "an" because from the input substring, it is the unique substring without overlapping with any the other characters.
Example 2:
Input:
str = "baabaabaaba"
Output:
baaba
Explanation:
From the input string "baabaabaaba", the longest repeating substring is "baabaabaaba," and the non-overlapping substring will be "baaba" because from the input substring, it is the unique substring without overlapping with any the other characters.
There are two different types of approaches for implementing the Longest Repeating and Non-Overlapping Substring,
- Navie Approach
- Dynamic Programming
i. Navie Approach
A Navie method for determining the longest non-overlapping repeating substring in Java is to iterate through the string and compare every possible substring to find out if it repeats.
Filename: LongestRepeatingNonOverlapping.java
public class LongestRepeatingNonOverlapping
{
public static String A(String str) // In the String str, the longest repeating non-overlapping is returned
{
int len = str.length();
String result = ""; // stores the result
int LongestLength = 0; // stores the length of the result
for (int i = 0; i < len; i++)
{
for (int j = i + 1; j <= len; j++) // overlapping
{
String substring = str.substring(i, j);
if (str.substring(j).contains(substring) && substring.length() > LongestLength) // maximum length of the substring is updated
{
result = substring;
LongestLength = substring.length();
}
}
}
return result;
}
public static void main(String[] args)
{
LongestRepeatingNonOverlapping lrno = new LongestRepeatingNonOverlapping();
String str1 = "baabaabaa";
String str2 = "banana";
String a = lrno.A(str1);
String b = lrno.A(str2);
System.out.println("Longest Repeating and Non-Overlapping Substring is: " + a);
System.out.println("Longest Repeating and Non-Overlapping Substring is: " + b);
}
}
Output:
Longest Repeating and Non-Overlapping Substring is: baa
Longest Repeating and Non-Overlapping Substring is: an
Explanation: Finds each possible substring in the input string and iterates through the string again for each substring to identify if it repeats itself later on the string without overlapping. If any is found, the longest repeated non-overlapping substring is applied to the result.
Time Complexity: This method is easy, but because of the three nested loops, it has an O(n^3) time complexity, making it inefficient, especially for larger strings.
ii. Dynamic Programming:
The task aims to optimize the solution by effectively storing and retrieving the previously computed substrings within the context of dynamic programming to identify the longest repeating and non-overlapping substring.
Filename: LongestRepeatingNonOverlapping.java
public class LongestRepeatingNonOverlapping
{
static String LongestRepeated(String str) // In the String str, the longest repeating non-overlapping is returned
{
int a = str.length();
int LRNO[][] = new int[a + 1][a + 1];
String res = ""; // stores the result
int len = 0; // stores the length of the result
int i, index = 0; // creating the table in bottom-up manner
for (i = 1; i <= a; i++)
{
for (int j = i + 1; j <= a; j++)
{
if (str.charAt(i - 1) == str.charAt(j - 1) && LRNO[i - 1][j - 1] < (j - i)) // overlapping
{
LRNO[i][j] = LRNO[i - 1][j - 1] + 1;
if (LRNO[i][j] > len) // maximum length of the substring is updated
{
len = LRNO[i][j];
index = Math.max(i, index);
}
}
else
{
LRNO[i][j] = 0;
}
}
}
if (len > 0)
{
for (i = index - len + 1; i <= index; i++)
{
res += str.charAt(i - 1);
}
}
return res;
}
public static void main(String[] args)
{
String str1 = "banana";
String str2 = "baabaabaaba";
System.out.println("Longest Repeating and Non-Overlapping Substring is: " + LongestRepeated(str1));
System.out.println("Longest Repeating Non-Overlapping Substring is: " + LongestRepeated(str2));
}
}
Output:
Longest Repeating and Non-Overlapping Substring is: an
Longest Repeating Non-Overlapping Substring is: baaba
Explanation: To store the lengths of the repeating non-overlapping substrings, it utilizes the 2D array LRNO. Continuously processing the string, it modifies the dynamic programming according to the equality and non-overlapping conditions of the characters. Finally, it selects the input string as the longest non-overlapping repeating substring.
Complexity: For longer strings, the dynamic programming method is more efficient than the naive solution method since it decreases the time complexity to O(n^2).
Conclusion:
In order to determine the longest repeating substring that does not overlap in occurrences, the "Longest Repeating and Non-Overlapping Substring" problem must be properly iterated through the string, using the dynamic programming for efficiency as it has the complexity of O(n^2), which is efficient than Navie Approach.