We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Longest Special Substring That Occurs Thrice II

Number: 3266

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a string s composed only of lowercase English letters, a substring is called special if it consists of exactly one distinct character (e.g., "aaa" or "zz"). The task is to determine the length of the longest special substring that occurs at least three times in s (overlapping occurrences count). If no such substring exists, return -1.

Key Insights

  • The special substring can only be formed by consecutive identical characters.
  • For any contiguous run of the same letter with length k, it produces (k - L + 1) substrings of length L.
  • We can aggregate counts by letter across all runs.
  • The count function for a fixed letter is monotonic with respect to L (if a certain L is achievable, so are smaller ones).
  • Use binary search over possible substring lengths to efficiently find the maximum L for which any letter produces at least 3 occurrences.

Space and Time Complexity

Time Complexity: O(26 * R * log(max_run)) where R is the number of runs (in worst-case O(n)) and max_run is the maximum run length in s.
Space Complexity: O(n) for storing run information.

Solution

The solution starts by traversing string s to identify runs of consecutive identical characters. We then use binary search over the possible substring lengths (from 1 to the maximum run length). For each candidate length L, for each letter we sum the counts from its runs (each contributing max(0, run_length - L + 1)). If any letter has a total count of at least three, L is valid. Continue with binary search to locate the maximum L meeting the criteria. Finally, if a valid special substring exists, its length is returned; otherwise, return -1.

Code Solutions

# Python solution
def findLongestSpecialSubstring(s: str) -> int:
    # Precompute the runs: list of tuples (char, run_length)
    runs = []
    n = len(s)
    start = 0
    while start < n:
        end = start
        while end < n and s[end] == s[start]:
            end += 1
        runs.append((s[start], end - start))
        start = end

    # Find maximum run length for binary search upper bound
    max_run = max(r for _, r in runs)
    
    # Check candidate substring length L is possible for any letter
    def can_find(L: int) -> bool:
        count_by_char = {}
        for ch, r in runs:
            # For a run to contribute, it must be at least length L.
            if r >= L:
                # count of substrings from this run is (r - L + 1)
                count_by_char[ch] = count_by_char.get(ch, 0) + (r - L + 1)
                # If any letter's total count is at least 3, return True
                if count_by_char[ch] >= 3:
                    return True
        return False

    # Binary search over possible lengths [1, max_run]
    lo, hi, ans = 1, max_run, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_find(mid):
            ans = mid  # mid length works
            lo = mid + 1  # try for longer substring
        else:
            hi = mid - 1
    return ans

# Example usage
print(findLongestSpecialSubstring("aaaa"))   # Expected output: 2
print(findLongestSpecialSubstring("abcdef")) # Expected output: -1
print(findLongestSpecialSubstring("abcaba")) # Expected output: 1
← Back to All Questions