2730. Find the Longest Semi-Repetitive Substring Medium

You are given a 0-indexed string s that consists of digits from 0 to 9.

A string t is called a semi-repetitive if there is at most one consecutive pair of the same characters inside t. For example, 0010, 002020, 0123, 2002, and 54944 are semi-repetitive while 00101022, and 1101234883 are not.

Return the length of the longest semi-repetitive substring inside s.

Example 1:
Input: s = "52233"
Output: 4
Explanation: The longest semi-repetitive substring is "5223", which starts at index 0 and ends at index 3.

Example 2:
Input: s = "5494"
Output: 4
Explanation: s is a semi-reptitive string, so the answer is 4.

Example 3:
Input: s = "1111111"
Output: 2
Explanation: The longest semi-repetitive substring is "11", which starts at index 0 and ends at index 1.

Approach

Input: A string s containing only digit characters (0-9)

Output: Return the length of the longest "semi-repetitive" substring — a contiguous string structure observing at most one side-by-side repetitive set.

This problem operates using the Variable-length Sliding Window architecture.

We leverage twin pointers mapping an active sliding window while holding an overarching integer variable (repeat_count) indicating current sequential duplicates recorded within frame dimensions. When adjacent replication frequencies transcend 1 overall set pair natively, it violates standard prerequisite conditions structuring "semi-repetitive" requirements, consequently mandating steady shifting of trailing left pointers inwards minimizing dimensions till conditions naturally conform to baseline definitions cleanly without interruption again.

While within optimal lawful dimensions continually validating properties progressively forward checking length scales extending, evaluate values establishing definitive maximum boundaries. Yield top length boundaries evaluated upon sequence traversal finish logic (minimum string limits always sit above 0 effectively 1 strictly).

Implementation

python

class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        left = 0                  # Left-bound sliding window frame dimension tracking
        repeat_count = 0          # Frequency variable mapping continuous overlapping sets contained internally 
        max_len = 1               # Maximal permissible valid fragment size discovered scaling linearly above basic element constraints 

        # Traverse indexing string from subsequent element '1'; treating pointer parameter 'right' as bounding border limits  
        for right in range(1, len(s)):
            # Tally consecutive matching pairs mapped back tracking string representations identical adjacently
            if s[right] == s[right - 1]:
                repeat_count += 1

            # Process overbooked strings possessing exceeding duplicates exceeding parameter thresholds > 1 actively contracting left dimension sequentially bounds 
            while repeat_count > 1:
                if s[left] == s[left + 1]:
                    repeat_count -= 1
                left += 1  # Reduce scaling constraint on trailing parameter linearly 

            # Keep tab registering optimal value representations comparing continuous dimensions iteratively 
            max_len = max(max_len, right - left + 1)

        return max_len  # Top substring outcome length provided dynamically mapping entire framework

javascript

var longestSemiRepetitiveSubstring = function(s) {
    let repeatStr = 0;

    let left = 0;
    let ans = 1;
    for (let right = 1; right < s.length; right++) {
        if (s[right] == s[right - 1]) repeatStr++;

        while (repeatStr > 1) {
            if (s[left] == s[left + 1]) repeatStr--;

            left++;
        }

        ans = Math.max(ans, right - left + 1);
    }

    return ans;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

2730. Find the Longest Semi-Repetitive Substring (English)2730. 找到最长的半重复子字符串 (Chinese)