The naive approach involves generating every possible substring, checking if it is "special," and then counting its total occurrences.

1. Generate all substrings of s using nested loops.
2. For each substring, iterate through its characters to verify if they are all identical.
3. If special, store it in a frequency map (Hash Map).
4. Finally, iterate through the map to find the longest key with a value $\ge 3$.

Pseudo-code:

text
max_len = -1
for i from 0 to n:
    for j from i to n:
        sub = s[i...j]
        if isSpecial(sub):
            map[sub]++

for sub, count in map:
    if count >= 3:
        max_len = max(max_len, sub.length)

Time Complexity: $O(N^3)$. Generating substrings is $O(N^2)$, and verifying/hashing each can take $O(N)$. Why it fails: While $N=50$ allows this to pass, this approach scales poorly. For larger constraints (like version II of this problem), $O(N^3)$ results in Time Limit Exceeded (TLE). It performs redundant checks on parts of the string that have already been processed.

Core Insight for Find Longest Special Substring That Occurs Thrice I

The key intuition is that we do not need to check arbitrary substrings like index 2 to 5. We only care about contiguous blocks of identical characters.

If we find a block like "aaaa" (length 4), this single block implicitly contains:

• One special substring of length 4 ("aaaa")
• Two special substrings of length 3 ("aaa")
• Three special substrings of length 2 ("aa")
• Four special substrings of length 1 ("a")

Invariant: The sliding window [left, right) always maintains a range of identical characters.

Visual Description: Imagine the window starting at the first character. The right pointer expands as long as s[right] matches s[left]. When s[right] differs, the window [left, right) represents a maximal special substring. We process this block to update our counts, then the left pointer jumps to right to begin a new window. This ensures we process the string in a single linear pass (plus a small inner loop for counting), drastically reducing complexity compared to brute force.

Execution Flow

Let's trace s = "aaaba":

1. Initialize: left = 0, counts map empty.
2. Iteration right = 0: s[0] is 'a'. Continue.
3. Iteration right = 1: s[1] is 'a' (matches s[left]). Continue.
4. Iteration right = 2: s[2] is 'a' (matches s[left]). Continue.
5. Iteration right = 3: s[3] is 'b' (mismatch!).
   • Process Window: [0, 3) is "aaa". Length $L=3$. Char 'a'.
   • Update counts for 'a':
     • Len 1: Add $3-1+1 = 3$. Total 'a' len 1 count: 3.
     • Len 2: Add $3-2+1 = 2$. Total 'a' len 2 count: 2.
   • Reset: Set left = 3.
6. Iteration right = 4: s[4] is 'a' (mismatch with s[left] which is 'b').
   • Process Window: [3, 4) is "b". Length $L=1$. Char 'b'.
   • Update counts for 'b':
     • Len 1: Add $1-1+1 = 1$. Total 'b' len 1 count: 1.
7. End of String: Loop finishes, but we have a remaining segment starting at left=4.
   • Process Window: [4, 5) is "a". Length $L=1$. Char 'a'.
   • Update counts for 'a':
     • Len 1: Add 1. Total 'a' len 1 count: $3 + 1 = 4$.
8. Final Check:
   • 'a', len 1: count 4 ($\ge 3$). Max result = 1.
   • 'a', len 2: count 2 ($< 3$).
   • 'b', len 1: count 1 ($< 3$).
   • Output: 1.

Proof of Correctness

The algorithm correctly identifies every maximal contiguous segment of identical characters. Since any "special" substring must be part of such a segment, processing these segments covers all possibilities. The formula $count += (L - k + 1)$ mathematically accounts for every valid position a substring of length $k$ could occupy within a block of length $L$. By aggregating these counts globally, we ensure that split occurrences (e.g., "aa...aa") are summed correctly.

Reference Implementation

C++ Solution for LeetCode 2981

cpp
#include <vector>
#include <string>
#include <algorithm>
#include <map>

using namespace std;

class Solution {
public:
    int maximumLength(string s) {
        int n = s.length();
        // count[char_index][length] stores frequency
        vector<vector<int>> count(26, vector<int>(n + 1, 0));
        
        int left = 0;
        
        for (int right = 0; right < n; ++right) {
            // Check if window breaks (next char differs) or we are at the end
            if (right == n - 1 || s[right] != s[right + 1]) {
                int len = right - left + 1;
                int charIdx = s[left] - 'a';
                
                // A block of length 'len' contributes to all sub-lengths
                for (int k = 1; k <= len; ++k) {
                    count[charIdx][k] += (len - k + 1);
                }
                
                // Move left to the start of the next block
                left = right + 1;
            }
        }
        
        int maxLen = -1;
        // Check all characters and lengths
        for (int i = 0; i < 26; ++i) {
            for (int len = n; len >= 1; --len) {
                if (count[i][len] >= 3) {
                    maxLen = max(maxLen, len);
                    break; // Optimization: found longest for this char
                }
            }
        }
        
        return maxLen;
    }
};

Java Solution for LeetCode 2981

java
class Solution {
    public int maximumLength(String s) {
        int n = s.length();
        // count[char_index][length]
        int[][] count = new int[26][n + 1];
        
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            // Detect end of a contiguous block
            if (right == n - 1 || s.charAt(right) != s.charAt(right + 1)) {
                int len = right - left + 1;
                int charIdx = s.charAt(left) - 'a';
                
                // Update frequencies for all valid sub-lengths within this block
                for (int k = 1; k <= len; k++) {
                    count[charIdx][k] += (len - k + 1);
                }
                
                // Reset window start
                left = right + 1;
            }
        }
        
        int maxLen = -1;
        for (int i = 0; i < 26; i++) {
            for (int len = n; len >= 1; len--) {
                if (count[i][len] >= 3) {
                    maxLen = Math.max(maxLen, len);
                    break; // Found max for this char
                }
            }
        }
        
        return maxLen;
    }
}

Python Solution for LeetCode 2981

python
class Solution:
    def maximumLength(self, s: str) -> int:
        n = len(s)
        # Dictionary to map (char, length) -> frequency
        counts = {}
        
        left = 0
        for right in range(n):
            # If current char is last char or next char is different
            if right == n - 1 or s[right] != s[right + 1]:
                length = right - left + 1
                char = s[left]
                
                # Update counts for all possible sub-lengths
                for k in range(1, length + 1):
                    key = (char, k)
                    # Formula: a block of length L has (L - k + 1) substrings of length k
                    counts[key] = counts.get(key, 0) + (length - k + 1)
                
                left = right + 1
        
        max_len = -1
        for (char, length), count in counts.items():
            if count >= 3:
                max_len = max(max_len, length)
                
        return max_len