Implement the solution to the Longest Repeated Non-Overlapping Substring problem using dynamic programming.?

The Longest Repeated Non-Overlapping Substring problem is to find the longest substring that occurs more than once in a given string, and the two occurrences of the substring must not overlap with each other.

To solve this problem with dynamic programming, we can use a similar approach as the Longest Common Substring problem, where we build a matrix to store the lengths of common substrings between all pairs of suffixes of the input string.

First, let’s define a 2D table, ‘dp‘, where ‘dp[i][j]‘ represents the length of the longest repeated non-overlapping substring that ends at indices ‘i‘ and ‘j‘ in the input string. Initially, all of the entries in ‘dp‘ are 0.

Then, we can iterate through all possible pairs of suffixes in the input string, and update the corresponding entry in ‘dp‘ if we find a repeated non-overlapping substring that ends at these suffixes. Specifically, if ‘s[i] == s[j]‘ and ‘i != j‘, we can update ‘dp[i][j]‘ as follows:

dp[i][j] = dp[i-1][j-1] + 1    if s[i-dp[i-1][j-1]:i] == s[j-dp[i-1][j-1]:j]
          max(dp[i-1][j], dp[i][j-1])    otherwise

The first case means that the longest repeated non-overlapping substring ends at ‘i‘ and ‘j‘ is the same as the longest repeated non-overlapping substring ending at ‘i-dp[i-1][j-1]-1‘ and ‘j-dp[i-1][j-1]-1‘, plus the current character. The second case means that the longest repeated non-overlapping substring ends at ‘i‘ and ‘j‘ must not overlap, so we take the maximum length of the longest repeated non-overlapping substring ending at ‘i-1‘ and ‘j‘, and the length of the longest repeated non-overlapping substring ending at ‘i‘ and ‘j-1‘.

Finally, we can find the maximum entry in ‘dp‘ and use its indices to retrieve the longest repeated non-overlapping substring in the input string.

Here’s the Java code to implement the above algorithm:

public static String longestRepeatedNonOverlappingSubstring(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    int maxLen = 0, maxEnd = 0;
    
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j) && i-dp[i-1][j-1] > 0 
                    && s.charAt(i-dp[i-1][j-1]-1) == s.charAt(j-dp[i-1][j-1]-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    maxEnd = i;
                }
            }
        }
    }
    
    return maxLen > 0 ? s.substring(maxEnd-maxLen+1, maxEnd+1) : "";
}

For example, if we call ‘longestRepeatedNonOverlappingSubstring("aabcaabcdaabcde")‘, it will return ‘"aabc"` as the longest repeated non-overlapping substring, as it appears twice in the input string and the two occurrences don’t overlap with each other.