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 II

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 the same character repeated.
  • We need to identify substrings that occur at least three times.
  • We can leverage a sliding window approach to find all special substrings of varying lengths.
  • A hash table can help track the occurrences of each special substring.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case, where n is the length of the string, due to nested loops for substring extraction.
Space Complexity: O(n), where n is the number of distinct special substrings stored in the hash table.

Solution

To solve the problem, we can use a combination of a sliding window and a hash table. The sliding window will help us identify special substrings of various lengths by expanding and contracting the window based on the character being processed. We'll keep a hash table to count the occurrences of each special substring. The algorithm proceeds as follows:

  1. Iterate through each character in the string.
  2. For each character, expand the window to form special substrings of increasing length.
  3. Store and count these substrings in a hash table.
  4. After collecting all special substrings, check which ones occur at least three times and keep track of the maximum length found.
  5. Return the maximum length or -1 if no substring occurs at least thrice.

Code Solutions

def longest_special_substring(s):
    count = {}
    n = len(s)
    
    # Iterate through the string to find special substrings
    for i in range(n):
        char = s[i]
        length = 1
        
        # Expand the window to find special substrings
        while i + 1 < n and s[i + 1] == char:
            length += 1
            i += 1
        
        # Count the occurrences of each special substring
        for l in range(1, length + 1):
            substring = char * l
            if substring in count:
                count[substring] += 1
            else:
                count[substring] = 1

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