Find Longest Special Substring That Occurs Thrice II

Find Longest Special Substring That Occurs Thrice II - 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "aaaa"

› Output: 2

💡 Note: Special substrings: "a" appears 4 times, "aa" appears 3 times, "aaa" appears 2 times, "aaaa" appears 1 time. The longest that occurs ≥3 times is "aa" with length 2.

Example 2 — Multiple Characters

$ Input: s = "abcdef"

› Output: -1

💡 Note: Each character appears only once, so no special substring can occur at least 3 times.

Example 3 — Mixed Pattern

$ Input: s = "abcaba"

› Output: 1

💡 Note: Only single characters are special here. "a" appears 3 times and "b" appears 2 times. The longest special substring that occurs ≥3 times is "a" with length 1.

Constraints

3 ≤ s.length ≤ 5 × 10⁴
s consists of only lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String with consecutive character blocks

Find Special Substrings

Identify all substrings with single character type

Count & Filter

Count occurrences and find longest with ≥3 occurrences

Key Takeaway

🎯 Key Insight: Use mathematical counting - in a block of n identical characters, there are exactly (n-k+1) substrings of length k

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is that for a consecutive block of identical characters of length n, we can mathematically calculate how many substrings of each length k exist (which is n-k+1). The optimal approach uses sliding window to find character blocks in O(n) time, then counts substring occurrences mathematically. Time: O(n), Space: O(26).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Mathematical Counting	O(n)	O(26)	Find consecutive character blocks and mathematically count substring occurrences
Binary Search on Answer	O(n log n)	O(n)	Binary search on substring length, check if that length can occur ≥3 times
Brute Force	O(n³)	O(n²)	Check every possible substring for specialness and count occurrences

Sliding Window with Mathematical Counting — Algorithm Steps

Identify consecutive character blocks using sliding window
For each block of length n, calculate substring counts
Count occurrences: k-length substring appears (n-k+1) times
Find longest substring with ≥3 occurrences

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Character Blocks

Identify consecutive identical character sequences

Mathematical Counting

For block length n, k-length substring appears (n-k+1) times

Sum Across Blocks

Add up occurrences across all blocks of same character

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 1000

typedef struct {
    char ch;
    int lengths[MAX_LEN];
    int count;
} CharBlock;

int solution(const char* s) {
    CharBlock blocks[26];
    int blockCount = 0;
    int n = strlen(s);
    int i = 0;
    
    // Initialize blocks
    for (int j = 0; j < 26; j++) {
        blocks[j].count = 0;
    }
    
    // Find consecutive character blocks
    while (i < n) {
        char ch = s[i];
        int count = 1;
        // Extend the block
        while (i + count < n && s[i + count] == ch) {
            count++;
        }
        
        // Find or create block for this character
        int blockIdx = -1;
        for (int j = 0; j < blockCount; j++) {
            if (blocks[j].ch == ch) {
                blockIdx = j;
                break;
            }
        }
        if (blockIdx == -1) {
            blocks[blockCount].ch = ch;
            blocks[blockCount].count = 0;
            blockIdx = blockCount++;
        }
        
        blocks[blockIdx].lengths[blocks[blockIdx].count++] = count;
        i += count;
    }
    
    int maxLength = -1;
    
    // For each character, check all possible substring lengths
    for (int b = 0; b < blockCount; b++) {
        CharBlock* block = &blocks[b];
        
        // Find max block length
        int maxBlockLen = 0;
        for (int j = 0; j < block->count; j++) {
            if (block->lengths[j] > maxBlockLen) {
                maxBlockLen = block->lengths[j];
            }
        }
        
        // Try each possible substring length
        for (int k = 1; k <= maxBlockLen; k++) {
            int totalOccurrences = 0;
            // Count how many times k-length substring appears
            for (int j = 0; j < block->count; j++) {
                if (block->lengths[j] >= k) {
                    totalOccurrences += block->lengths[j] - k + 1;
                }
            }
            
            if (totalOccurrences >= 3) {
                if (k > maxLength) {
                    maxLength = k;
                }
            }
        }
    }
    
    return maxLength;
}

int main() {
    char s[MAX_LEN];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find blocks + constant work per character type

✓ Linear Growth

Space Complexity

O(26)

Store at most 26 character types with their block lengths

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

348 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Mathematical Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler