# Find Longest Special Substring That Occurs Thrice I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-i)
Canonical: https://scaleengineer.com/dsa/problems/find-longest-special-substring-that-occurs-thrice-i
**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
---
## 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 <= 50`
* `s` consists of only lowercase English letters.

# Approaches
## Brute-force Substring Generation and Counting
This approach systematically checks every possible length for a special substring, from the largest possible down to the smallest. For each length, it checks every possible special substring (e.g., "aaa", "bbb", etc.) and counts its occurrences in the input string. The first length found to have a special substring appearing at least three times is the answer.
**Time:** O(N^3). The outer loop for length `L` runs `N` times. The character loop is constant (26). The inner loop for counting runs `O(N)` times. String creation and comparison take `O(L)` time. This gives a total complexity of `O(N * 26 * (L + N*L))`, which simplifies to `O(N^3)` as `L` can be up to `N`. · **Space:** O(N), where N is the length of the string. This space is used to store the `specialStr` being checked, which can have a length up to N.
**Pros:** Simple to understand and implement.; Correct and guaranteed to find the solution.
**Cons:** The time complexity is cubic, which can be slow for larger constraints, although it passes for `N <= 50`.; It performs many redundant string comparisons.
### Explanation
The algorithm iterates through possible lengths `L` from `s.length()` down to 1. For each length `L`, it iterates through all 26 lowercase English letters, from 'a' to 'z'. For each character `c`, it constructs a "special string" `target` of length `L` consisting only of character `c`. It then counts how many times this `target` string appears as a substring in the input string `s`. To count occurrences, it slides a window of size `L` across `s` and checks for equality with `target`. If the count for any `target` string is 3 or more, it means we have found the longest special substring that meets the criteria (since we are iterating `L` downwards). The algorithm can immediately return `L`. If the loops complete without finding such a substring, it means none exists, and the function returns -1.

```java
class Solution {
    public int maximumLength(String s) {
        int n = s.length();
        // Iterate from the largest possible length down to 1
        for (int len = n; len >= 1; len--) {
            // Check for each character 'a' through 'z'
            for (char c = 'a'; c <= 'z'; c++) {
                // Build the special string to search for
                StringBuilder sb = new StringBuilder();
                for (int k = 0; k < len; k++) {
                    sb.append(c);
                }
                String specialStr = sb.toString();
                
                int count = 0;
                // Count occurrences of the special string
                for (int i = 0; i <= n - len; i++) {
                    if (s.substring(i, i + len).equals(specialStr)) {
                        count++;
                    }
                }
                
                // If found 3 or more times, this is the max length
                if (count >= 3) {
                    return len;
                }
            }
        }
        return -1;
    }
}
```
### Algorithm
1. Initialize `n = s.length()`.
2. Iterate through all possible lengths `L` from `n` down to 1.
3. For each length `L`, iterate through all 26 lowercase English letters, `c` from 'a' to 'z'.
4. Construct a special string `specialStr` of length `L` consisting only of character `c`.
5. Initialize a counter `count = 0`.
6. Iterate through the input string `s` with a sliding window of size `L` (from index `i = 0` to `n - L`).
7. For each window, extract the substring `sub` and check if it equals `specialStr`.
8. If they are equal, increment `count`.
9. After checking all windows, if `count` is 3 or more, it means we have found a valid special substring. Since we are iterating `L` from largest to smallest, this is the longest possible length. Return `L` immediately.
10. If the loops complete without returning, no special substring occurs at least three times. Return -1.

## Binary Search on the Answer
This approach leverages the monotonic property of the problem: if a special substring of length `k` occurs at least three times, then any shorter special substring (derived from it) of length `j < k` also occurs at least three times. This allows us to use binary search on the possible lengths of the special substring.
**Time:** O(N^2 * log N). The binary search performs `O(log N)` calls to the `check` function. The `check` function iterates through the string `O(N)` times, and substring operations inside it take `O(L)` time, where `L` is the length being checked. This results in `O(N * L)` for the check. The total complexity is `O(N * L * log N)`, which is `O(N^2 * log N)` in the worst case. · **Space:** O(L), where L is the length being checked. The map in the `check` function stores at most 26 distinct special substrings. The space for each key is `L`, so the total space is `O(26 * L) = O(L)`.
**Pros:** More efficient than the brute-force approach.; Reduces the search space for the answer logarithmically.
**Cons:** More complex to implement due to the binary search framework and the helper function.; Still not the most optimal solution.
### Explanation
We define a search range for the answer (the length `L`) from 1 to `s.length()`. We perform a binary search within this range. For each `mid` value (a potential length), we check if it's possible to find *any* special substring of that length that occurs at least three times. This check is done in a helper function, `check(length)`. The `check(length)` function works by generating all special substrings of the given `length` and counting their occurrences using a hash map. It iterates through the string `s`, identifies all special substrings of the target `length`, and stores their counts. If any count reaches 3, `check` returns `true`. If `check(mid)` returns `true`, it means a length of `mid` is achievable, so we store it as a potential answer and try for a larger length by setting `low = mid + 1`. If `check(mid)` returns `false`, the length `mid` is too long, so we search for a smaller length by setting `high = mid - 1`. The final answer is the largest length for which `check` returned `true`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maximumLength(String s) {
        int low = 1, high = s.length();
        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) { // Length must be at least 1
                low = mid + 1;
                continue;
            }
            if (check(s, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(String s, int len) {
        Map<String, Integer> counts = new HashMap<>();
        int n = s.length();
        for (int i = 0; i <= n - len; i++) {
            String sub = s.substring(i, i + len);
            if (isSpecial(sub)) {
                counts.put(sub, counts.getOrDefault(sub, 0) + 1);
                if (counts.get(sub) >= 3) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isSpecial(String str) {
        char first = str.charAt(0);
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i) != first) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
1. Define a search range for the answer (the length `L`) from `1` to `s.length()`. Initialize `ans = -1`.
2. Perform a binary search. While `low <= high`:
   a. Calculate `mid = low + (high - low) / 2`.
   b. Call a helper function `check(mid)` to determine if any special substring of length `mid` occurs at least three times.
   c. If `check(mid)` is `true`, it means length `mid` is possible. We store it (`ans = mid`) and try for a longer one (`low = mid + 1`).
   d. If `check(mid)` is `false`, length `mid` is not possible. We must try a shorter one (`high = mid - 1`).
3. Return `ans`.

**`check(length)` function:**
1. Create a map `counts` to store `(special_substring, count)`.
2. Iterate `i` from 0 to `s.length() - length`.
3. Extract `sub = s.substring(i, i + length)`.
4. Check if `sub` is a special string.
5. If it is, increment its count in the map.
6. If the count for `sub` becomes 3, return `true` immediately.
7. If the loop finishes, no special substring of the given length occurred 3 times, so return `false`.

## Grouping Consecutive Characters and Optimized Counting
This is the most optimal approach. It works by first preprocessing the string to identify all contiguous blocks of identical characters (e.g., "aaa", "bb", "c"). Any special substring must be entirely contained within one of these blocks. By analyzing the lengths of these blocks for each character, we can efficiently determine the longest possible special substring that can be formed at least three times.
**Time:** O(N log K), where N is the length of the string and K is the maximum number of contiguous blocks for any single character (K <= N). The initial pass to group characters is `O(N)`. The dominant step is sorting the lists of lengths. Since the total number of blocks is at most N, the total time for sorting is bounded, making the overall complexity effectively `O(N log N)` in the worst case. · **Space:** O(N), where N is the string length. The `groups` map stores the lengths of all contiguous blocks. The total number of integers stored across all lists in the map is at most N.
**Pros:** Highly efficient and optimal.; Processes the string in a single pass followed by sorting, which is very fast.
**Cons:** The logic for combining counts from different groups is more complex to reason about and implement correctly compared to simpler approaches.
### Explanation
First, we iterate through the string `s` once to find all maximal contiguous blocks of the same character. We store the lengths of these blocks in a map, where the key is the character and the value is a list of its block lengths. For example, for `s = "aaabbbaaccc"`, the map would be `{'a': [3, 2], 'b': [4], 'c': [3]}`. For each character `c` in the map, we sort its list of block lengths in descending order. Let the sorted lengths be `l_1, l_2, l_3, ...`. Now, for a special string of length `L` to occur three times, the occurrences can come from one, two, or three different blocks:
1.  **From one block:** The longest block `l_1` must be long enough to contain the substring three times. A block of length `l_1` contains a substring of length `L` exactly `l_1 - L + 1` times. For this to be `>= 3`, we need `L <= l_1 - 2`. The maximum possible `L` is `l_1 - 2`.
2.  **From two blocks:** The longest block `l_1` provides two occurrences (`L <= l_1 - 1`), and the second-longest `l_2` provides one (`L <= l_2`). The maximum `L` is `min(l_1 - 1, l_2)`.
3.  **From three blocks:** The top three blocks `l_1, l_2, l_3` each provide one occurrence. This requires `L <= l_3`. The maximum `L` is `l_3`.
For each character, we calculate the maximum `L` possible by taking the maximum of the results from these three cases. The final answer is the overall maximum `L` found across all characters.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int maximumLength(String s) {
        Map<Character, List<Integer>> groups = new HashMap<>();
        int n = s.length();
        int i = 0;
        while (i < n) {
            char c = s.charAt(i);
            int j = i;
            while (j < n && s.charAt(j) == c) {
                j++;
            }
            int length = j - i;
            groups.computeIfAbsent(c, k -> new ArrayList<>()).add(length);
            i = j;
        }

        int maxLength = 0;
        for (List<Integer> lengths : groups.values()) {
            Collections.sort(lengths, Collections.reverseOrder());
            
            // Case 1: One group provides all 3 occurrences
            if (lengths.get(0) >= 3) {
                maxLength = Math.max(maxLength, lengths.get(0) - 2);
            }

            // Case 2: Two groups provide the 3 occurrences
            if (lengths.size() >= 2) {
                // l1 provides 2 occurrences, l2 provides 1
                if (lengths.get(0) >= 2) {
                    maxLength = Math.max(maxLength, Math.min(lengths.get(0) - 1, lengths.get(1)));
                }
            }
            
            // Case 3: Three groups provide 1 occurrence each
            if (lengths.size() >= 3) {
                maxLength = Math.max(maxLength, lengths.get(2));
            }
        }

        return maxLength > 0 ? maxLength : -1;
    }
}
```
### Algorithm
1. Create a `Map<Character, List<Integer>> groups` to store lengths of contiguous character blocks.
2. Iterate through `s` with a pointer `i`. At each position, find the end `j` of the contiguous block of `s.charAt(i)`.
3. Add the length `j - i` to the list for `s.charAt(i)` in the `groups` map. Update `i = j`.
4. Initialize `maxLength = 0`.
5. For each character `c` and its list of `lengths` in the map:
   a. Sort `lengths` in descending order.
   b. Calculate the max possible length `L` from three scenarios:
      i. **One block:** If `l_1` exists, max `L` is `l_1 - 2`.
      ii. **Two blocks:** If `l_1, l_2` exist, max `L` is `min(l_1 - 1, l_2)`.
      iii. **Three blocks:** If `l_1, l_2, l_3` exist, max `L` is `l_3`.
   c. Update `maxLength` with the maximum `L` found for character `c`.
6. After checking all characters, if `maxLength > 0`, return `maxLength`. Otherwise, return -1.

# 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

```