Find the Longest Semi-Repetitive Substring - Video Solutions

Problem Overview: Given a numeric string s, return the length of the longest substring that is semi-repetitive. A substring is semi-repetitive if it contains at most one pair of equal adjacent characters (for example "11"). The goal is to scan the string and keep the longest window where this condition holds.

Approach 1: Sliding Window (O(n) time, O(1) space)

This problem fits naturally into a sliding window pattern. Maintain two pointers left and right that represent the current substring window. While expanding the window to the right, count how many adjacent equal pairs appear (i.e., when s[i] == s[i-1]). If the count exceeds one, move the left pointer forward until the window again contains at most one such pair. Each character enters and leaves the window at most once, so the scan runs in O(n) time with constant extra memory. This approach is optimal and very common in substring problems involving constraints.

Approach 2: Dynamic Programming Tracking Adjacent Pairs (O(n) time, O(1) space)

A dynamic programming view keeps track of the most recent index where an adjacent duplicate occurred. While iterating through the string, store the index of the previous duplicate pair and the one before it. If a new pair appears, update the window start to the position after the earlier pair so that the substring still contains at most one duplicate pair. This effectively maintains the longest valid substring ending at each position. The algorithm still performs a single pass through the string, giving O(n) time and constant space. Some implementations describe this as DP because the current state depends on previously tracked pair positions.

Recommended for interviews: The sliding window solution is the approach most interviewers expect. It demonstrates strong control over substring constraints and two-pointer techniques. A brute-force enumeration of all substrings would show understanding but runs in O(n^2) or worse. The optimal sliding window solution proves you can maintain constraints efficiently while scanning the string once.