# Find Longest Special Substring That Occurs Thrice II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-longest-special-substring-that-occurs-thrice-ii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Hash Table, String
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
You are given a string `s` that consists of lowercase English letters.

A string is called **special** if it is made up of only a single character. For example, the string `"abc"` is not special, whereas the strings `"ddd"`, `"zz"`, and `"f"` are special.

Return _the length of the **longest special substring** of_ `s` _which occurs **at least thrice**_, _or_ `-1` _if no special substring occurs at least thrice_.

A **substring** is a contiguous **non-empty** sequence of characters within a string.

**Example 1:**

**Input:** s = "aaaa"
**Output:** 2
**Explanation:** The longest special substring which occurs thrice is "aa": substrings "**aa**aa", "a**aa**a", and "aa**aa**".
It can be shown that the maximum length achievable is 2.

**Example 2:**

**Input:** s = "abcdef"
**Output:** -1
**Explanation:** There exists no special substring which occurs at least thrice. Hence return -1.

**Example 3:**

**Input:** s = "abcaba"
**Output:** 1
**Explanation:** The longest special substring which occurs thrice is "a": substrings "**a**bcaba", "abc**a**ba", and "abcab**a**".
It can be shown that the maximum length achievable is 1.

**Constraints:**

* `3 <= s.length <= 5 * 105`
* `s` consists of only lowercase English letters.

# Approaches
## Binary Search on the Answer
This approach leverages the monotonic nature of the problem. If a special substring of length `L` occurs at least three times, any shorter special substring of the same character also occurs at least three times. This allows us to binary search for the maximum possible length `L`. We define a search space for `L` from `1` to `n` and, for each candidate length `mid`, we check if it's possible to find a special substring of that length occurring thrice. If it is, we try for a larger length; otherwise, we try for a smaller one.
**Time:** O(N log N). The pre-processing step to find all character blocks takes O(N). The binary search performs O(log N) iterations. Inside each iteration, the `check` function iterates through all blocks, which takes O(B) time where B is the total number of blocks (B <= N). Thus, the total time is O(N + B * log N), which simplifies to O(N log N). · **Space:** O(N), where N is the length of the string. This space is used to store the lengths of the contiguous blocks of characters. In the worst case (e.g., "ababab..."), there can be O(N) blocks.
**Pros:** Significantly more efficient than brute-force approaches, passing the time limits for the given constraints.; It's a classic and powerful technique for problems with monotonic properties.
**Cons:** Slightly less efficient than the optimal linear time solution.; The implementation involves a main function for binary search and a helper function for checking, which can be more complex than a single integrated loop.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maximumLength(String s) {
        int n = s.length();
        List<List<Integer>> groups = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            groups.add(new ArrayList<>());
        }

        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            groups.get(s.charAt(i) - 'a').add(j - i);
            i = j;
        }

        int ans = -1;
        int low = 1, high = n;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) { // Length 0 is not a valid substring
                low = mid + 1;
                continue;
            }
            if (check(mid, groups)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(int len, List<List<Integer>> groups) {
        for (int i = 0; i < 26; i++) {
            long count = 0;
            for (int groupLen : groups.get(i)) {
                if (groupLen >= len) {
                    count += (groupLen - len + 1);
                }
            }
            if (count >= 3) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
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.

## Linear Time Scan and Grouping
A more optimal approach solves the problem in linear time. Instead of searching for the answer, we can directly compute it. The key insight is that for any given character, the maximum length of a special substring that occurs at least three times depends only on the lengths of its three longest contiguous blocks. By finding these top three block lengths for each character, we can calculate the maximum possible length in constant time per character and solve the entire problem in a single pass over the data.
**Time:** O(N). The first pass to find and group block lengths takes O(N). The second phase involves iterating through 26 characters and for each, finding the top 3 block lengths. Since each block length is processed once, this step is also proportional to the total number of blocks, which is at most N. Therefore, the total time complexity is O(N). · **Space:** O(N), where N is the length of the string. This space is required to store the lists of block lengths for each character. The worst-case space is O(N) for an alternating string like "ababab...".
**Pros:** This is the most efficient solution with an optimal O(N) time complexity.; It avoids the overhead of the binary search loop and computes the result directly.
**Cons:** The logic to determine the maximum length from the top three block lengths (`k1`, `k2`, `k3`) is more nuanced and requires careful case analysis to prove its correctness.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maximumLength(String s) {
        int n = s.length();
        // groups[i] stores a list of lengths of contiguous blocks of character 'a' + i
        List<List<Integer>> groups = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            groups.add(new ArrayList<>());
        }

        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            groups.get(s.charAt(i) - 'a').add(j - i);
            i = j;
        }

        int maxLen = 0;
        for (int c = 0; c < 26; c++) {
            List<Integer> lengths = groups.get(c);
            if (lengths.isEmpty()) {
                continue;
            }
            
            // Find top 3 lengths for the current character in O(number of blocks)
            int k1 = 0, k2 = 0, k3 = 0;
            for (int len : lengths) {
                if (len > k1) {
                    k3 = k2;
                    k2 = k1;
                    k1 = len;
                } else if (len > k2) {
                    k3 = k2;
                    k2 = len;
                } else if (len > k3) {
                    k3 = len;
                }
            }

            // Case 1: 3 substrings from the longest block
            if (k1 >= 3) {
                maxLen = Math.max(maxLen, k1 - 2);
            }
            
            // Case 2: 2 from the longest, 1 from the second longest
            if (k1 >= 2 && k2 >= 1) {
                maxLen = Math.max(maxLen, Math.min(k1 - 1, k2));
            }
            
            // Case 3: 1 from each of the top 3
            if (k3 >= 1) {
                maxLen = Math.max(maxLen, k3);
            }
        }

        return maxLen == 0 ? -1 : maxLen;
    }
}
```
### Algorithm
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.

# Solutions
### Java

```java
class Solution {
private
  String s;
private
  int n;
public
  int maximumLength(String s) {
    this.s = s;
    n = s.length();
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l == 0 ? -1 : l;
  }
private
  boolean check(int x) {
    int[] cnt = new int[26];
    for (int i = 0; i < n;) {
      int j = i + 1;
      while (j < n && s.charAt(j) == s.charAt(i)) {
        j++;
      }
      int k = s.charAt(i) - 'a';
      cnt[k] += Math.max(0, j - i - x + 1);
      if (cnt[k] >= 3) {
        return true;
      }
      i = j;
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumLength(string s) {
    int n = s.size();
    int l = 0, r = n;
    auto check = [&](int x) {
      int cnt[26]{};
      for (int i = 0; i < n;) {
        int j = i + 1;
        while (j < n && s[j] == s[i]) {
          ++j;
        }
        int k = s[i] - 'a';
        cnt[k] += max(0, j - i - x + 1);
        if (cnt[k] >= 3) {
          return true;
        }
        i = j;
      }
      return false;
    };
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l == 0 ? -1 : l;
  }
};

```

### Python

```python
class Solution:
    def maximumLength(self, s: str) -> int: def check(x: int) -> bool: cnt = defaultdict(int) i = 0 while i < n: j = i + 1 while j < n and s[j] == s[i]: j += 1 cnt[s[i]] += max(0, j - i - x + 1) i = j return max(cnt . values()) >= 3 n = len(s) l, r = 0, n while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return - 1 if l == 0 else l

```