#2730

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Find the Longest Semi-Repetitive Substring

Find the length of the longest substring where at most one adjacent pair of digits repeats, using a sliding window approach.

string sliding window

Problem Statement

Given a string s consisting of digits from 0 to 9, find the length of its longest semi-repetitive substring. A semi-repetitive substring contains at most one pair of consecutive identical digits.

Return the maximum length of any substring that satisfies this semi-repetitive property. For example, in s = "52233", the substring "5223" is valid because it contains only one adjacent pair (22) and its length is 4.

Examples

Example 1

Input: s = "52233"

Output: 4

The longest semi-repetitive substring is "5223". Picking the whole string "52233" has two adjacent same digit pairs 22 and 33, but at most one is allowed.

Example 2

Input: s = "5494"

Output: 4

s is a semi-repetitive string.

Example 3

Input: s = "1111111"

Output: 2

The longest semi-repetitive substring is "11". Picking the substring "111" has two adjacent same digit pairs, but at most one is allowed.

Constraints

1 <= s.length <= 50
'0' <= s[i] <= '9'

Solution Approach

Sliding Window with Tracking

Use two pointers to define a window. Track if an adjacent pair has already appeared. Expand the right pointer while maintaining the semi-repetitive condition. If a second repeat occurs, move the left pointer past the first repeat.

Update Maximum Length

Each time the window is valid, calculate its length and update the maximum length. This ensures the solution always reflects the longest semi-repetitive substring encountered so far.

Optimizations for Small n

Since s.length is at most 50, you could also check every substring directly. For each substring, count adjacent repeats and update the maximum if it remains semi-repetitive. This brute-force approach is acceptable due to small input size.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) using the sliding window because each character is visited at most twice. Space complexity is O(1) as only counters and two pointers are needed.

What Interviewers Usually Probe

Candidate must handle the edge case where all digits are identical.
Look for efficient tracking of repeated adjacent digits within the window.
Watch if the candidate correctly resets the window after the second repeat occurs.

Common Pitfalls or Variants

Common pitfalls

Counting repeated pairs incorrectly and allowing more than one in the window.
Failing to update the maximum length after shifting the window.
Not handling the first or last character correctly when checking adjacent repeats.

Follow-up variants

Find the longest substring allowing up to k adjacent repeated pairs instead of 1.
Count the number of longest semi-repetitive substrings instead of returning length.
Apply the same logic to a string with letters instead of digits, still using the semi-repetitive rule.

FAQ

What defines a semi-repetitive substring in this problem?

A semi-repetitive substring contains at most one pair of consecutive identical digits, any more breaks the rule.

Can the entire string be semi-repetitive?

Yes, if the string contains at most one adjacent repeated pair, the entire string can be counted as the longest substring.

Is a sliding window necessary for small inputs?

Not strictly; for s.length up to 50, a brute-force check of every substring works but sliding window is more efficient and scalable.

How do I handle multiple adjacent repeats?

Stop expanding the window when a second adjacent repeat appears, then move the start pointer past the first repeat to maintain semi-repetitive property.

Does this solution pattern apply to other strings?

Yes, the sliding window with running state updates can be applied to any sequence where you need to track limited repeated patterns.

terminal

Solution

Solution 1: Two Pointers

We use two pointers to maintain a range $s[j..i]$ such that there is at most one pair of adjacent characters that are equal, initially $j = 0$, $i = 1$. Initialize the answer $ans = 1$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        ans, n = 1, len(s)
        cnt = j = 0
        for i in range(1, n):
            cnt += s[i] == s[i - 1]
            while cnt > 1:
                cnt -= s[j] == s[j + 1]
                j += 1
            ans = max(ans, i - j + 1)
        return ans

Solution 2: Two Pointers (Optimization)

Since the problem only requires us to find the length of the longest semi-repetitive substring, each time the number of adjacent identical characters in the interval exceeds $1$, we can move the left pointer $l$ once, while the right pointer $r$ continues to move to the right. This ensures that the length of the substring does not decrease.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        ans, n = 1, len(s)
        cnt = j = 0
        for i in range(1, n):
            cnt += s[i] == s[i - 1]
            while cnt > 1:
                cnt -= s[j] == s[j + 1]
                j += 1
            ans = max(ans, i - j + 1)
        return ans

Continue Practicing

#2781 length of the longest valid substring #2904 shortest and lexicographically smallest beautiful string #2516 take k of each character from left and right