Find Longest Special Substring That Occurs Thrice I

Find Longest Special Substring That Occurs Thrice I - 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 Special Substrings

$ Input: s = "aaaa"

› Output: 2

💡 Note: Special substrings: "a" occurs 4 times, "aa" occurs 3 times, "aaa" occurs 2 times (less than 3). The longest special substring that occurs at least thrice is "aa" with length 2.

Example 2 — Mixed Characters

$ Input: s = "abcdef"

› Output: -1

💡 Note: Each character appears only once, so no special substring can occur 3 or more times. Return -1.

Example 3 — Multiple Character Runs

$ Input: s = "abcaba"

› Output: 1

💡 Note: Only "a" and "b" can form special substrings. Character "a" appears 3 times total, character "b" appears 2 times. Only "a" occurs at least 3 times, so return length 1.

Constraints

3 ≤ s.length ≤ 50
s consists of only lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input String

String with consecutive character runs

Find Special Substrings

Identify substrings of same character

Count Occurrences

Return longest length appearing ≥3 times

Key Takeaway

🎯 Key Insight: Count consecutive character runs instead of generating all substrings for optimal performance

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to analyze consecutive runs of each character rather than generating all substrings. For each character, we can mathematically calculate how many special substrings of each length can be formed from its runs. Best approach uses character run analysis with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Character Run Analysis	O(n)	O(n)	Smart analysis of consecutive character runs to find maximum valid length
Frequency Count with HashMap	O(n²)	O(n²)	Count all special substrings using a hash map to track frequencies
Brute Force - Check All Substrings	O(n³)	O(1)	Generate all special substrings and count their occurrences

Optimized Character Run Analysis — Algorithm Steps

Group consecutive runs by character
For each character, sort run lengths in descending order
For each possible length, calculate total occurrences across all runs
Return maximum length with ≥3 occurrences

Visualization

Tap to expand

Step-by-Step Walkthrough

Group Runs

Organize consecutive runs by character

Calculate Counts

For each length, sum possible substrings across runs

Find Maximum

Return longest length with count ≥ 3

Code -

solution.c — C

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

#define MAX_CHARS 26
#define MAX_RUNS 1000

struct CharRuns {
    char ch;
    int runs[MAX_RUNS];
    int count;
};

int compare(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);  // Descending order
}

int solution(char* s) {
    int n = strlen(s);
    if (n == 0) return -1;
    
    struct CharRuns charData[MAX_CHARS];
    int charCount = 0;
    
    // Initialize
    for (int k = 0; k < MAX_CHARS; k++) {
        charData[k].count = 0;
    }
    
    // Find all consecutive runs for each character
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && s[j] == s[i]) {
            j++;
        }
        
        // Find or create entry for this character
        int found = -1;
        for (int k = 0; k < charCount; k++) {
            if (charData[k].ch == s[i]) {
                found = k;
                break;
            }
        }
        
        if (found == -1 && charCount < MAX_CHARS) {
            found = charCount++;
            charData[found].ch = s[i];
            charData[found].count = 0;
        }
        
        if (found >= 0 && charData[found].count < MAX_RUNS) {
            charData[found].runs[charData[found].count++] = j - i;
        }
        
        i = j;
    }
    
    int maxLength = -1;
    
    // For each character, find the maximum valid length
    for (int c = 0; c < charCount; c++) {
        // Sort runs by length descending
        qsort(charData[c].runs, charData[c].count, sizeof(int), compare);
        
        // Try each possible length from 1 to max_run_length
        int maxRun = charData[c].runs[0];
        for (int length = 1; length <= maxRun; length++) {
            int count = 0;
            // Count how many times this length can appear
            for (int r = 0; r < charData[c].count; r++) {
                if (charData[c].runs[r] >= length) {
                    count += charData[c].runs[r] - length + 1;
                }
            }
            
            if (count >= 3) {
                if (length > maxLength) {
                    maxLength = length;
                }
            }
        }
    }
    
    return maxLength;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find runs, then process each character's runs (bounded by string length)

✓ Linear Growth

Space Complexity

O(n)

Store run lengths for each character (at most n runs total)

⚡ Linearithmic Space

8.4K Views

Medium Frequency

~15 min Avg. Time

156 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

Optimized Character Run Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler