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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Longest Special Substring That Occurs Thrice I

Difficulty: Medium

Problem Description

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. 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.

Key Insights

  • A special substring consists of repeated identical characters.
  • The task is to find substrings that occur at least three times in the input string.
  • The length of the special substrings can vary; we need to find the maximum length that meets the occurrence requirement.
  • We can use a sliding window approach or hash table to count occurrences of special substrings.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

To solve this problem, we can use a combination of substring generation and counting:

  1. Iterate through the string to generate all possible special substrings of varying lengths.
  2. Use a hash table (or dictionary) to count how many times each special substring occurs.
  3. Finally, check the counts and determine the maximum length of any substring that occurs at least thrice.

This approach leverages the fact that special substrings are made up of the same character and can be easily counted using a hash table.

Code Solutions

def longest_special_substring(s):
    from collections import defaultdict
    
    count = defaultdict(int)
    n = len(s)
    
    # Generate all possible special substrings
    for i in range(n):
        char = s[i]
        length = 1
        while i + 1 < n and s[i + 1] == char:
            length += 1
            count[char * length] += 1
            i += 1
        count[char] += 1  # Count single character

    # Find the longest special substring that occurs at least thrice
    max_length = -1
    for substring, occ in count.items():
        if occ >= 3:
            max_length = max(max_length, len(substring))
    
    return max_length
← Back to All Questions