Longest substring that occurs Thrice II

XXX. Maximum Length of Repeated Substring

Dynamic Programming

String

Problem Statement:

Given a string s, find the maximum length of any substring that can occur three times within the string, ensuring each occurrence is non-overlapping.

Algorithm:

1. Iterate through the string while keeping track of the current substring length for each character.
2. Maintain an array to store the three longest lengths of substrings for each character.
3. Update the array dynamically by replacing the smallest length if the current substring length exceeds it.
4. Find the character with the maximum value of its minimum length among the top three lengths.

Complexity:

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we only use fixed-size data structures.

Java Implementation:

public int maximumLength(String s) {
    int substringLength = 0, ans = -1;
    char previousCharacter = '\0';
    int[][] substringLengths = new int[26][3];

    // Initialize the substringLengths array to -1
    for (int charIdx = 0; charIdx < 26; charIdx++) 
        for (int lenIdx = 0; lenIdx < 3; lenIdx++) 
            substringLengths[charIdx][lenIdx] = -1;

    for (char character : s.toCharArray()) {
        if (character == previousCharacter) {
            substringLength++;
        } else {
            substringLength = 1;
            previousCharacter = character;
        }

        // Replace the minimum frequency with the current length if it is greater
        int index = character - 'a';
        int minLength = min(
            substringLengths[index][0],
            substringLengths[index][1],
            substringLengths[index][2]
        );
        if (substringLength > minLength) {
            if (substringLengths[index][0] == minLength) 
                substringLengths[index][0] = substringLength;
            else if (substringLengths[index][1] == minLength) 
                substringLengths[index][1] = substringLength;
            else 
                substringLengths[index][2] = substringLength;
        }
    }

    // Find the character with the maximum value of its minimum frequency
    for (int charIdx = 0; charIdx < 26; charIdx++) {
        ans = Math.max(
            ans,
            min(
                substringLengths[charIdx][0],
                substringLengths[charIdx][1],
                substringLengths[charIdx][2]
            )
        );
    }

    return ans;
}

// Method to return the minimum of three values
public int min(int a, int b, int c) {
    return a < Math.min(b, c) ? a : Math.min(b, c);
}

Hello, World!