Find Longest Special Substring That Occurs Thrice II

1. Monotonicity: The core idea is that if a special substring of length L can be found at least three times, then any special substring of the same character with a length k < L can also be found at least three times. This monotonic property allows us to use binary search on the answer (the length L).
2. Binary Search Setup: We define a search range for the length L from 1 to n, where n is the length of the string s. Let's call this range [low, high].
3. check(L) Function: For a given length L (the mid value in the binary search), we need a helper function check(L) to determine if there exists any special substring of length L that occurs at least three times.
   • To implement check(L) efficiently, we first pre-process the string s to find all contiguous blocks of identical characters. We can store the lengths of these blocks grouped by character (e.g., in a List<List<Integer>> where the outer list index corresponds to the character 'a' through 'z').
   • Inside check(L), we iterate through each character from 'a' to 'z'.
   • For each character, we calculate the total number of special substrings of length L we can form from all its blocks. A single block of length K can provide K - L + 1 such substrings, provided K >= L.
   • We sum these contributions. If the total count for any character reaches 3 or more, check(L) returns true.
   • If we iterate through all characters and none meet the condition, check(L) returns false.
4. Search Loop:
   • If check(mid) is true, it means a length of mid is achievable. We store mid as a potential answer and try for a longer substring by setting low = mid + 1.
   • If check(mid) is false, the length mid is too long. We must try a shorter one by setting high = mid - 1.
5. Result: The binary search continues until low > high. The last successfully checked length is our answer. If no length is ever successful, we return -1.

The algorithm performs a binary search on the possible lengths of the special substring. The range of possible lengths is from 1 to n, the length of the input string s.

For each candidate length L tested by the binary search, a helper function check(L) is called. This function first requires a one-time pre-processing step (done before the binary search starts) to find all contiguous blocks of identical characters in s and group their lengths by character. For example, for s = "aaabaaa", the groups would be a: [3, 3] and b: [1].

The check(L) function then iterates through each of the 26 possible characters. For a given character, it sums up how many special substrings of length L can be formed from its blocks. A block of length K contributes K - L + 1 substrings of length L. If the total count for any character is 3 or more, check(L) returns true, indicating that length L is achievable.

Based on the result of check(L), the binary search range is narrowed down until the maximum possible length is found. If the loop completes without ever finding a valid length, it means no special substring occurs thrice, and we return -1.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int maximumLength(String s) {6        int n = s.length();7        List<List<Integer>> groups = new ArrayList<>();8        for (int i = 0; i < 26; i++) {9            groups.add(new ArrayList<>());10        }11 12        int i = 0;13        while (i < n) {14            int j = i;15            while (j < n && s.charAt(j) == s.charAt(i)) {16                j++;17            }18            groups.get(s.charAt(i) - 'a').add(j - i);19            i = j;20        }21 22        int ans = -1;23        int low = 1, high = n;24 25        while (low <= high) {26            int mid = low + (high - low) / 2;27            if (mid == 0) { // Length 0 is not a valid substring28                low = mid + 1;29                continue;30            }31            if (check(mid, groups)) {32                ans = mid;33                low = mid + 1;34            } else {35                high = mid - 1;36            }37        }38        return ans;39    }40 41    private boolean check(int len, List<List<Integer>> groups) {42        for (int i = 0; i < 26; i++) {43            long count = 0;44            for (int groupLen : groups.get(i)) {45                if (groupLen >= len) {46                    count += (groupLen - len + 1);47                }48            }49            if (count >= 3) {50                return true;51            }52        }53        return false;54    }55}

1. Group Block Lengths: First, iterate through the input string s to identify all contiguous blocks of identical characters. Group the lengths of these blocks by character. A Map<Character, List<Integer>> or a List<List<Integer>> of size 26 is perfect for this. This step takes O(N) time.
2. Find Top 3 Lengths: For each character, we only need the lengths of its three longest blocks to determine the maximum possible length. Iterate through the 26 characters. For each character's list of block lengths, find the three largest values (k1 >= k2 >= k3). This can be done in a single pass over the list of lengths for that character, without needing to sort the entire list.
3. Calculate Maximum Length per Character: For each character, calculate the longest special substring that can occur thrice. This is the maximum of three possibilities, which cover all ways to pick 3 substrings:
   • From 3 blocks: Take one substring from each of the top three blocks. The maximum possible length is limited by the smallest of these blocks, so the length is k3.
   • From 2 blocks: Take two substrings from the longest block (k1) and one from the second-longest (k2). The length L must satisfy L <= k1 - 1 (to get two from k1) and L <= k2. Thus, the maximum length is min(k1 - 1, k2).
   • From 1 block: Take all three substrings from the single longest block (k1). The length L must satisfy L <= k1 - 2. The maximum length is k1 - 2.
4. Find Overall Maximum: The answer to the problem is the maximum length found across all 26 characters. Keep a global maximum variable, update it with the result from each character, and return it. If the final maximum length is 0, it means no special substring occurred three times, so return -1 as required.

This approach directly calculates the maximum possible length without searching. It works in two main phases.

First, we parse the string s to find all contiguous blocks of identical characters. We store the lengths of these blocks, grouped by character. For instance, for s = "aaabaaa", we would record that character 'a' has blocks of lengths [3, 3] and 'b' has a block of length [1].

Second, we iterate through each of the 26 possible characters. For each character, we find the lengths of its three longest blocks, let's call them k1, k2, and k3 in descending order. Then, we consider all the ways to form three occurrences of a special substring:

1. From the single longest block (k1): We can get 3 substrings of length k1 - 2.
2. From the two longest blocks (k1, k2): We can get 2 from k1 and 1 from k2. The max length is min(k1 - 1, k2).
3. From the three longest blocks (k1, k2, k3): We can get 1 from each. The max length is k3.

The maximum of these three values gives the longest special substring for that specific character. We do this for all characters and take the overall maximum. If the result is 0, no such substring exists, so we return -1.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int maximumLength(String s) {6        int n = s.length();7        // groups[i] stores a list of lengths of contiguous blocks of character 'a' + i8        List<List<Integer>> groups = new ArrayList<>();9        for (int i = 0; i < 26; i++) {10            groups.add(new ArrayList<>());11        }12 13        int i = 0;14        while (i < n) {15            int j = i;16            while (j < n && s.charAt(j) == s.charAt(i)) {17                j++;18            }19            groups.get(s.charAt(i) - 'a').add(j - i);20            i = j;21        }22 23        int maxLen = 0;24        for (int c = 0; c < 26; c++) {25            List<Integer> lengths = groups.get(c);26            if (lengths.isEmpty()) {27                continue;28            }29            30            // Find top 3 lengths for the current character in O(number of blocks)31            int k1 = 0, k2 = 0, k3 = 0;32            for (int len : lengths) {33                if (len > k1) {34                    k3 = k2;35                    k2 = k1;36                    k1 = len;37                } else if (len > k2) {38                    k3 = k2;39                    k2 = len;40                } else if (len > k3) {41                    k3 = len;42                }43            }44 45            // Case 1: 3 substrings from the longest block46            if (k1 >= 3) {47                maxLen = Math.max(maxLen, k1 - 2);48            }49            50            // Case 2: 2 from the longest, 1 from the second longest51            if (k1 >= 2 && k2 >= 1) {52                maxLen = Math.max(maxLen, Math.min(k1 - 1, k2));53            }54            55            // Case 3: 1 from each of the top 356            if (k3 >= 1) {57                maxLen = Math.max(maxLen, k3);58            }59        }60 61        return maxLen == 0 ? -1 : maxLen;62    }63}