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 the Longest Semi-Repetitive Substring

Difficulty: Medium

Problem Description

You are given a digit string s that consists of digits from 0 to 9. A string is called semi-repetitive if there is at most one adjacent pair of the same digit. Return the length of the longest semi-repetitive substring of s.

Key Insights

  • A semi-repetitive substring contains at most one pair of adjacent identical digits.
  • We can use a sliding window approach to maintain a substring while checking for the number of adjacent pairs.
  • We need to efficiently track the pairs of adjacent digits as we expand and contract our window.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. We traverse the string at most twice (once for expanding the window and once for contracting it). Space Complexity: O(1), as we only use a fixed amount of extra space for counters and pointers regardless of the input size.

Solution

We will use a sliding window approach to find the longest semi-repetitive substring. The algorithm will maintain two pointers (left and right) to represent the current window. As we expand the right pointer to include more characters in the window, we will check for the number of adjacent pairs. If the count exceeds one, we will move the left pointer to shrink the window until we have at most one pair. Throughout the process, we will keep track of the maximum length of valid windows found.

Code Solutions

def longest_semi_repetitive_substring(s: str) -> int:
    left = 0
    max_length = 0
    pair_count = 0

    for right in range(len(s)):
        # Check for adjacent duplicates
        if right > 0 and s[right] == s[right - 1]:
            pair_count += 1

        # If there are more than one adjacent pairs, move left pointer
        while pair_count > 1:
            if s[left] == s[left + 1]:
                pair_count -= 1
            left += 1

        # Update the maximum length of the valid substring
        max_length = max(max_length, right - left + 1)

    return max_length
← Back to All Questions