Coding Problem: Find Longest Special Substring That Occurs Thrice I

Finding the Longest Repeating Character Substring

Problem Statement:

Given a string `s`, we need to find the length of the longest special substring that occurs at least three times. A special substring is a contiguous sequence of identical characters.

Solution Approach:

We can solve this problem efficiently using a sliding window technique and a hash map to keep track of character frequencies within the window.

Python Implementation

def longestRepeating(s):
    """
    Finds the length of the longest special substring occurring at least thrice.

    Args:
        s: The input string.

    Returns:
        The length of the longest special substring, or -1 if not found.
    """

    n = len(s)
    char_count = {}
    max_len = 0
    left = 0

    for right in range(n):
        char_count[s[right]] = char_count.get(s[right], 0) + 1

        # If the current character occurs more than 3 times, shrink the window
        while char_count[s[right]] > 3:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1

        # Update the maximum length if we find a special substring of length 3 or more
        if len(char_count) == 1 and list(char_count.values())[0] >= 3:
            max_len = max(max_len, right - left + 1)

    return max_len
    

Explanation:

1. Initialize Variables:
   • `n`: Length of the input string.
   • `char_count`: A hash map to store the frequency of characters within the window.
   • `max_len`: To store the maximum length of the special substring found so far.
   • `left`: Left pointer of the sliding window.
2. Iterate Over the String:
   • For each character `s[right]`, increment its frequency in `char_count`.
   • If the frequency of `s[right]` exceeds 3, we need to shrink the window from the left until the frequency becomes 3 or less.
   • If the window contains only one unique character with a frequency of 3 or more, update `max_len`.
3. Return the Result:
   • After processing the entire string, `max_len` will hold the length of the longest special substring.

Time and Space Complexity:

• Time Complexity: O(N), where N is the length of the string.
• Space Complexity: O(1), as the hash map will store at most 26 characters (for lowercase English letters).

Resource	Link
Follow us on Linkedin	Click Here
Ways to get your next job	Click Here
How your resume should be to attract companies	Click Here
Check Out Jobs	Click Here
Read our blogs	Click Here