Find Longest Special Substring That Occurs Thrice I

LeetCode 2981: Find Longest Special Substring That Occurs Thrice I Solution & Explanation

Problem Overview

TL;DR: Use a variable-size sliding window to group contiguous identical characters, calculate the frequency of all special substrings derived from these groups, and return the maximum length occurring at least three times.

In LeetCode 2981, "Find Longest Special Substring That Occurs Thrice I", you are given a string s. You must identify the length of the longest substring that meets two criteria:

1. It is special (composed of a single unique character, e.g., "aaa").
2. It appears at least three times in the original string.

If no such substring exists, return -1. While the constraints for this specific version (I) are small ($N \le 50$), the logic required is foundational for handling larger string constraints efficiently.

Brute Force Approach for Find Longest Special Substring That Occurs Thrice I

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:

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.

Algorithm Strategy: Sliding Window Patterns

1. State Management: maintain a 2D array or a map counts where counts[char][length] stores the frequency of a special substring of a specific length made of char.
2. Window Initialization: Initialize left at 0.
3. Expansion: Iterate right from 0 to n.
4. Condition Check:
   • We treat the window as a contiguous block of identical characters.
   • We detect the end of a block when right == n (end of string) or s[right] != s[left].
5. Processing:
   • When a block ends, calculate its length L = right - left.
   • The character is c = s[left].
   • This block contributes to the counts of all special substrings of length $1$ to $L$. Specifically, a block of length $L$ contains $(L - k + 1)$ occurrences of a special substring of length $k$.
   • Update the counts data structure accordingly.
6. Contraction/Reset: Move left to right to start measuring the next block of characters.
7. Result: After the loop, scan the counts structure. Return the maximum length $k$ such that any character has counts[char][k] >= 3.

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.
     • Len 3: Add $3-3+1 = 1$. Total 'a' len 3 count: 1.
   • 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.
   • Reset: Set left = 4.
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.

Pattern Reuse Notes

The Sliding Window - Variable Size pattern is versatile and appears in many popular interview questions:

• LeetCode 3: Longest Substring Without Repeating Characters - Uses a similar expansion/contraction logic but tracks character uniqueness instead of homogeneity.
• LeetCode 76: Minimum Window Substring - Expands to satisfy frequency counts, then shrinks to minimize length.
• LeetCode 209: Minimum Size Subarray Sum - Expands to meet a sum threshold, then shrinks to find the minimal size.
• LeetCode 219: Contains Duplicate II - Maintains a window of fixed size (or variable constrained by distance) to find duplicates.

Reference Implementation

C++ Solution for LeetCode 2981

1#include <vector>
2#include <string>
3#include <algorithm>
4#include <map>
5
6using namespace std;
7
8class Solution {
9public:
10    int maximumLength(string s) {
11        int n = s.length();
12        // count[char_index][length] stores frequency
13        vector<vector<int>> count(26, vector<int>(n + 1, 0));
14        
15        int left = 0;
16        
17        for (int right = 0; right < n; ++right) {
18            // Check if window breaks (next char differs) or we are at the end
19            if (right == n - 1 || s[right] != s[right + 1]) {
20                int len = right - left + 1;
21                int charIdx = s[left] - 'a';
22                
23                // A block of length 'len' contributes to all sub-lengths
24                for (int k = 1; k <= len; ++k) {
25                    count[charIdx][k] += (len - k + 1);
26                }
27                
28                // Move left to the start of the next block
29                left = right + 1;
30            }
31        }
32        
33        int maxLen = -1;
34        // Check all characters and lengths
35        for (int i = 0; i < 26; ++i) {
36            for (int len = n; len >= 1; --len) {
37                if (count[i][len] >= 3) {
38                    maxLen = max(maxLen, len);
39                    break; // Optimization: found longest for this char
40                }
41            }
42        }
43        
44        return maxLen;
45    }
46};

Java Solution for LeetCode 2981

1class Solution {
2    public int maximumLength(String s) {
3        int n = s.length();
4        // count[char_index][length]
5        int[][] count = new int[26][n + 1];
6        
7        int left = 0;
8        
9        for (int right = 0; right < n; right++) {
10            // Detect end of a contiguous block
11            if (right == n - 1 || s.charAt(right) != s.charAt(right + 1)) {
12                int len = right - left + 1;
13                int charIdx = s.charAt(left) - 'a';
14                
15                // Update frequencies for all valid sub-lengths within this block
16                for (int k = 1; k <= len; k++) {
17                    count[charIdx][k] += (len - k + 1);
18                }
19                
20                // Reset window start
21                left = right + 1;
22            }
23        }
24        
25        int maxLen = -1;
26        for (int i = 0; i < 26; i++) {
27            for (int len = n; len >= 1; len--) {
28                if (count[i][len] >= 3) {
29                    maxLen = Math.max(maxLen, len);
30                    break; // Found max for this char
31                }
32            }
33        }
34        
35        return maxLen;
36    }
37}

Python Solution for LeetCode 2981

1class Solution:
2    def maximumLength(self, s: str) -> int:
3        n = len(s)
4        # Dictionary to map (char, length) -> frequency
5        counts = {}
6        
7        left = 0
8        for right in range(n):
9            # If current char is last char or next char is different
10            if right == n - 1 or s[right] != s[right + 1]:
11                length = right - left + 1
12                char = s[left]
13                
14                # Update counts for all possible sub-lengths
15                for k in range(1, length + 1):
16                    key = (char, k)
17                    # Formula: a block of length L has (L - k + 1) substrings of length k
18                    counts[key] = counts.get(key, 0) + (length - k + 1)
19                
20                left = right + 1
21        
22        max_len = -1
23        for (char, length), count in counts.items():
24            if count >= 3:
25                max_len = max(max_len, length)
26                
27        return max_len