Problem Description

You are given a string s that contains only digits from 0 to 9.

A string is called semi-repetitive if it contains at most one adjacent pair of identical digits. In other words, there can be at most one place where two consecutive characters are the same.

Examples of semi-repetitive strings:

• "0010" - has one adjacent pair (00)
• "002020" - has one adjacent pair (00)
• "0123" - has no adjacent pairs
• "2002" - has one adjacent pair (00)
• "54944" - has one adjacent pair (44)

Examples of strings that are NOT semi-repetitive:

• "00101022" - has two adjacent pairs (00 and 22)
• "1101234883" - has two adjacent pairs (11 and 88)

Your task is to find the length of the longest substring of s that is semi-repetitive. A substring is a contiguous sequence of characters within the string.

For example, if s = "52233", the longest semi-repetitive substring would be "5223" (which has only one adjacent pair: 22), giving a length of 4.

The solution uses a sliding window approach with two pointers (j and i) to maintain a valid window. The variable cnt tracks how many adjacent pairs of identical digits exist in the current window. When cnt exceeds 1, the left pointer j is moved right until the window becomes valid again (having at most one adjacent pair). The maximum window size encountered is tracked and returned as the answer.

Intuition

The key insight is recognizing that this is a sliding window problem. We need to find the longest contiguous portion of the string that satisfies a specific constraint - having at most one pair of adjacent identical digits.

Think of it like this: we want to expand our window as much as possible while keeping it valid. A window is valid when it contains at most one pair of consecutive identical digits.

We can start with two pointers at the beginning of the string and expand the right pointer. As we expand, we keep track of how many pairs of adjacent identical digits we have in our current window.

The moment we encounter more than one pair (making our window invalid), we need to shrink from the left. We keep shrinking until we remove one of the pairs, making our window valid again.

Why does this work? Because:

1. We want the longest substring, so we should try to expand our window as much as possible
2. When we have too many pairs (more than 1), the only way to fix it is to remove characters from the beginning of our window
3. We don't need to check all possible substrings - the sliding window naturally explores all potentially optimal solutions

The counting mechanism is clever: we increment cnt when we find an adjacent pair while expanding right, and decrement cnt when we pass over an adjacent pair while shrinking from the left. This efficiently tracks the number of adjacent pairs in our current window without having to rescan the entire window each time.

This approach gives us an optimal O(n) time complexity since each character is visited at most twice - once by the right pointer and once by the left pointer.

Learn more about Sliding Window patterns.

Solution Approach

We implement a two-pointer sliding window approach to find the longest semi-repetitive substring.

Variables Setup:

• j = 0: Left pointer of our sliding window
• i: Right pointer that iterates through the string starting from index 1
• cnt = 0: Counter for the number of adjacent pairs of identical digits in our current window
• ans = 1: Stores the maximum length found (initialized to 1 since any single character is semi-repetitive)

Algorithm Steps:

1. Expand the window: We iterate through the string with pointer i starting from index 1:

   for i in range(1, n):

2. Count adjacent pairs: When we include a new character at position i, we check if it forms a pair with the previous character:

   cnt += s[i] == s[i - 1]

   If s[i] == s[i - 1] is true, we've found an adjacent pair and increment cnt.

3. Shrink if invalid: When cnt > 1 (more than one adjacent pair), we need to shrink from the left:

   while cnt > 1:
       cnt -= s[j] == s[j + 1]
       j += 1

   • Before moving j forward, we check if positions j and j + 1 form an adjacent pair
   • If they do, we decrement cnt since we're removing this pair from our window
   • Move j forward to shrink the window

4. Update maximum length: After ensuring our window is valid (at most 1 adjacent pair):

   ans = max(ans, i - j + 1)

   The current window size is i - j + 1.

Why this works:

• The window s[j..i] always maintains the invariant of having at most one adjacent pair
• By only moving j when necessary (when cnt > 1), we ensure we're always considering the longest possible valid substring ending at position i
• The algorithm explores all possible valid substrings efficiently in linear time

Time Complexity: O(n) where n is the length of the string, as each character is visited at most twice.

Space Complexity: O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the algorithm with s = "52233".

Initial State:

• n = 5, j = 0, cnt = 0, ans = 1
• Window: empty initially

Step 1: i = 1

• Check if s[1] == s[0] → '2' == '5' → False
• cnt remains 0 (no adjacent pairs)
• Window: [j=0, i=1] → "52"
• Update ans = max(1, 1-0+1) = 2

Step 2: i = 2

• Check if s[2] == s[1] → '2' == '2' → True
• cnt = 1 (found one adjacent pair: 22)
• cnt ≤ 1, so no shrinking needed
• Window: [j=0, i=2] → "522"
• Update ans = max(2, 2-0+1) = 3

Step 3: i = 3

• Check if s[3] == s[2] → '3' == '2' → False
• cnt remains 1
• Window: [j=0, i=3] → "5223"
• Update ans = max(3, 3-0+1) = 4

Step 4: i = 4

• Check if s[4] == s[3] → '3' == '3' → True
• cnt = 2 (now have two adjacent pairs: 22 and 33)
• Need to shrink! cnt > 1:
  • Check if s[0] == s[1] → '5' == '2' → False
  • cnt remains 2
  • Move j = 1
  • Still cnt > 1, continue shrinking:
  • Check if s[1] == s[2] → '2' == '2' → True
  • cnt = 1 (removed the 22 pair)
  • Move j = 2
  • Now cnt = 1, stop shrinking
• Window: [j=2, i=4] → "233"
• Update ans = max(4, 4-2+1) = 4

Final Answer: 4

The longest semi-repetitive substring is "5223" with length 4, containing only one adjacent pair (22).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

The algorithm uses a two-pointer sliding window approach. The outer loop iterates through each character from index 1 to n-1, which takes O(n) time. The inner while loop might seem to add complexity, but each element can only be visited by the j pointer at most once throughout the entire execution. The j pointer only moves forward and never resets, moving from 0 to at most n-1 across all iterations. Therefore, the total number of operations is bounded by 2n (each element is visited at most twice - once by i and once by j), which simplifies to O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space. The variables ans, n, cnt, j, and i are all single integer values that don't scale with the input size. No additional data structures like arrays, lists, or hash maps are created. The space used remains constant regardless of the input string length.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Initialization of Answer Variable

The Problem: A common mistake is initializing the answer variable to 0 instead of 1. This causes issues when the input string has length 1.

Incorrect Code:

max_length = 0  # Wrong initialization!

Why it fails:

• For a single-character string like "5", the loop never executes (since we start from index 1)
• The function returns 0, but the correct answer should be 1
• Any single character is a valid semi-repetitive substring

Correct Solution:

max_length = 1  # Correct initialization

Pitfall 2: Off-by-One Error When Checking Adjacent Pairs

The Problem: When shrinking the window, developers often confuse which indices to check for forming an adjacent pair.

Incorrect Code:

while consecutive_pairs_count > 1:
    if s[left - 1] == s[left]:  # Wrong indices!
        consecutive_pairs_count -= 1
    left += 1

Why it fails:

• When left = 0, accessing s[left - 1] causes an index out of bounds error
• Even if it doesn't crash, it's checking the wrong pair - we need to check if removing the character at left breaks a pair with its successor

Correct Solution:

while consecutive_pairs_count > 1:
    if s[left] == s[left + 1]:  # Check left with its successor
        consecutive_pairs_count -= 1
    left += 1

Pitfall 3: Forgetting to Update Answer Inside the Loop

The Problem: Some implementations only update the answer after the loop completes, missing optimal windows during iteration.

Incorrect Code:

for right in range(1, string_length):
    if s[right] == s[right - 1]:
        consecutive_pairs_count += 1
  
    while consecutive_pairs_count > 1:
        if s[left] == s[left + 1]:
            consecutive_pairs_count -= 1
        left += 1

# Only updating answer once at the end - Wrong!
return right - left + 1

Why it fails:

• The final window might not be the longest valid window
• For example, with input "52233", the algorithm might end with a smaller window than the maximum encountered during processing

Correct Solution:

for right in range(1, string_length):
    # ... window adjustment logic ...
  
    # Update answer at each iteration
    current_window_length = right - left + 1
    max_length = max(max_length, current_window_length)

Pitfall 4: Not Handling Edge Cases Properly

The Problem: Failing to handle edge cases like empty strings or strings with all identical characters.

Scenarios to consider:

• Empty string (though typically problem constraints specify minimum length)
• String of length 1
• String with all identical characters like "1111"
• String with no adjacent pairs like "12345"

Robust Solution:

def longestSemiRepetitiveSubstring(self, s: str) -> int:
    # Handle edge case
    if len(s) <= 1:
        return len(s)
  
    # Rest of the implementation...