Find the Longest Semi-Repetitive Substring

Find the Longest Semi-Repetitive Substring - Problem

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. For example, "0010", "002020", "0123", "2002", and "54944" are semi-repetitive while the following are not: "00101022" (adjacent same digit pairs are 00 and 22), and "1101234883" (adjacent same digit pairs are 11 and 88).

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

Input & Output

Example 1 — Basic Case

$ Input: s = "52233"

› Output: 4

💡 Note: The longest semi-repetitive substring is "5223" with length 4. It has exactly one adjacent pair (2,2).

Example 2 — No Adjacent Pairs

$ Input: s = "5494"

› Output: 4

💡 Note: The entire string "5494" has no adjacent pairs, so it's completely semi-repetitive with length 4.

Example 3 — Multiple Pairs

$ Input: s = "1111"

› Output: 2

💡 Note: Any substring longer than 2 would have more than one adjacent pair. Maximum is "11" with length 2.

Constraints

1 ≤ s.length ≤ 1000
s consists of digits from 0 to 9

Visualization

Tap to expand

Understanding the Visualization

Input

String with digits 0-9

Process

Find substrings with ≤1 adjacent pair

Output

Length of longest valid substring

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently find the longest substring with at most one adjacent pair

Asked in

G Google 25 a Amazon 15

The key insight is to use a sliding window approach to maintain at most one adjacent pair. Best approach is sliding window with O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window	O(n)	O(1)	Use two pointers to maintain a window with at most one adjacent pair
Brute Force	O(n³)	O(1)	Check all possible substrings and find the longest semi-repetitive one

Sliding Window — Algorithm Steps

Start with left and right pointers at beginning
Expand right pointer and count adjacent pairs
If pairs exceed 1, contract left pointer
Track maximum window size

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with left and right pointers

Expand

Move right pointer and count pairs

Contract

Move left pointer when constraint violated

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    if (n <= 1) return n;
    
    int left = 0;
    int pairs = 0;
    int maxLen = 1;
    
    for (int right = 1; right < n; right++) {
        // Check if we found a new adjacent pair
        if (s[right] == s[right - 1]) {
            pairs++;
        }
        
        // If we have more than 1 pair, shrink window
        while (pairs > 1) {
            if (s[left] == s[left + 1]) {
                pairs--;
            }
            left++;
        }
        
        int windowSize = right - left + 1;
        if (windowSize > maxLen) {
            maxLen = windowSize;
        }
    }
    
    return maxLen;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each character is visited at most twice (once by each pointer)

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track pointers and counts

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler