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

Number: 2786

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a digit string s, find the length of the longest contiguous substring that is semi-repetitive, where a substring is called semi-repetitive if it contains at most one pair of adjacent identical digits.

Key Insights

  • Use a sliding window (two-pointer) approach to efficiently inspect substrings.
  • As you extend the window, count the number of adjacent duplicate pairs.
  • When the count exceeds one, shrink the window from the left until the count is at most one again.
  • Care should be taken when adjusting the count when the left pointer moves past a duplicate pair boundary.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s, because each character is processed at most twice. Space Complexity: O(1), as only a few variables are used.

Solution

We use a two-pointer or sliding window approach:

  1. Initialize two pointers (“left” and “right”) at the start of the string.
  2. Keep a counter for the number of adjacent duplicate pairs found within the current window.
  3. As you move the “right” pointer:
    • If the current character is the same as the previous, increment the duplicate counter.
  4. If the counter exceeds one (meaning more than one adjacent duplicate pair exists), move the “left” pointer forward. While doing so, if a duplicate pair that is leaving the window is encountered (i.e., if s[left] equals s[left + 1]), decrement the counter.
  5. Track and update the maximum window length where the duplicate counter remains at most one.
  6. Return the maximum length found.

Code Solutions

# Python solution using sliding window approach

def longestSemiRepetitiveSubstring(s: str) -> int:
    left = 0
    duplicate_count = 0
    max_length = 1  # At least one character is always valid

    # iterate with right pointer through the string
    for right in range(1, len(s)):
        # if current character is same as previous, we found a duplicate pair
        if s[right] == s[right - 1]:
            duplicate_count += 1

        # shrink the window from the left until there is at most one duplicate pair
        while duplicate_count > 1:
            # if there's a duplicate pair at the beginning of the window, decrement the count
            if left + 1 < len(s) and s[left] == s[left + 1]:
                duplicate_count -= 1
            left += 1  # move left pointer to shrink the window

        # update max_length with the current window size
        current_window_length = right - left + 1
        max_length = max(max_length, current_window_length)

    return max_length

# Example usage:
print(longestSemiRepetitiveSubstring("52233"))  # Output: 4
← Back to All Questions