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 I

Number: 3267

Difficulty: Medium

Paid? No

Companies: Google, Meta

Problem Description

Given a string s consisting of lowercase English letters, find the length of the longest special substring (a contiguous substring composed of a single repeated character) that occurs at least three times in s (occurrences may overlap). If no such substring exists, return -1.

Key Insights

  • A "special" substring is one that contains only a single repeated character.
  • Occurrences of the substring can overlap; e.g., for "aaaa", the substring "aa" appears three times.
  • We can break the string into contiguous runs of the same character. For each run of length k, any special substring of that character with length L can appear (k - L + 1) times.
  • For each letter from 'a' to 'z', sum up the counts from all runs in s to determine if a special substring of a given length occurs at least three times.
  • Iterate over all possible lengths from 1 to |s| (since s is small, |s| ≤ 50) and track the maximum valid L.

Space and Time Complexity

Time Complexity: O(26 * n^2) where n is the length of the string. (n is at most 50.) Space Complexity: O(1) additional space.

Solution

We iterate over each possible character from 'a' to 'z'. For each letter, we sweep through the string to identify runs (contiguous segments) of that letter. For every run of length k, a special substring of length L is available with (k - L + 1) occurrences if k >= L. We then sum these occurrences across all runs for that letter. If the total occurrences for a given L are at least 3, then L is a candidate answer. By checking for all characters and all candidate L, we can determine the maximum valid substring length.

The algorithm leverages:

  • Iteration over all 26 lowercase letters.
  • A simple one-pass scan of the string to compute contiguous runs.
  • Counting possible substrings in each run using (run length - L + 1).
  • Brute-force checking over possible substring lengths due to small input constraint.

Code Solutions

# Python solution
def findLongestSpecialSubstring(s: str) -> int:
    max_length = -1
    n = len(s)
    # Iterate over each letter in the alphabet
    for char in "abcdefghijklmnopqrstuvwxyz":
        # List to store lengths of consecutive runs for the current char
        run_lengths = []
        i = 0
        while i < n:
            if s[i] == char:
                start = i
                # Count length of current run of char
                while i < n and s[i] == char:
                    i += 1
                run_lengths.append(i - start)
            else:
                i += 1
        # For each possible special substring length L from 1 to n
        for L in range(1, n+1):
            occurrence_count = 0
            # Sum possible occurrences from all runs of current char
            for run in run_lengths:
                if run >= L:
                    occurrence_count += (run - L + 1)
            # Check if current candidate meets the requirement
            if occurrence_count >= 3:
                max_length = max(max_length, L)
    return max_length

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