1062. Longest Repeating Substring

Given a string s, return the length of the longest repeating substrings. If no repeating substring exists, return 0.

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.

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase English letters.

Solution:

class Solution {
    public int longestRepeatingSubstring(String s) {
        int result = 0;
        /*
        a   b   b   a   b   a
        i   
                    j
                s        
                            s2
        */

        for (int i = 0; i < s.length(); i++){
            char curI = s.charAt(i);

            for (int j = i + 1; j < s.length() ; j++){
                if (s.charAt(i) == s.charAt(j)){
                    int start = i;
                    int start2 = j;
                    while(start2 < s.length() && s.charAt(start) == s.charAt(start2)){
                        start++;
                        start2++;
                    }
                    result = Math.max(result, start - i);
                }
            }
        }

        return result;
    }
}
// TC: O(n^2)
// SC: O(1)

class Solution {
    public int longestRepeatingSubstring(String s) {
        int length = s.length();

        int[][] dp = new int[length + 1][length +1];

        for (int i = 1; i <= length; i++){
            for (int j = i + 1; j <= length; j++){
                // If characters match, extend the length of 
                // the common substring

                if (s.charAt(i - 1) == s.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }

        return maxLength;
    }
}

// TC: O(n^2)
// SC: O(n^2)