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.
Example 1:
Input: s = "52233"
Output: 4
Explanation:
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
Explanation:
s is a semi-repetitive string.
Example 3:
Input: s = "1111111"
Output: 2
Explanation:
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'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.
This approach employs a sliding window strategy to keep track of semi-repetitive substrings. The window will expand by moving the end pointer through the string. If the window contains more than one adjacent pair of the same digits, the start pointer will increment to maintain the semi-repetitive property. This method efficiently finds the longest valid substring in linear time.
The function uses a single loop to adjust the sliding window's end pointer. It keeps count of adjacent similar digit pairs and adjusts the start pointer as necessary to ensure that no more than one pair exists in the window. By doing this, the function dynamically assesses and updates the longest valid substring's length.
Python
JavaScript
The algorithm runs in O(n) time complexity, where n is the length of the string, as each character is processed once. Its space complexity is O(1), as it uses a fixed amount of extra space.
The dynamic programming approach involves creating a table that stores the length of the longest semi-repetitive substring ending at each character. This table is updated incrementally by considering previous computations to find an optimal solution. The approach ensures that only allowable adjacent pairs are counted to maintain valid substrings.
The logic here is to update the length of the potential substring at each step, keeping the adjacent counter in check. Whenever more than one adjacent pair is detected, the dynamic calculation is reset, ensuring no invalid patterns extend beyond their limits.
The complexity here is also O(n) time due to a single traversal of the string. Space complexity remains O(1) as no additional data structures are used beyond primitive types.
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.
We use cnt to record the number of pairs of adjacent characters that are equal in the range. If cnt > 1, then we need to move the left pointer j until cnt \le 1. Each time, we update the answer as ans = max(ans, i - j + 1).
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
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.
Finally, the answer is n - l, where n is the length of the string.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | The algorithm runs in O(n) time complexity, where n is the length of the string, as each character is processed once. Its space complexity is O(1), as it uses a fixed amount of extra space. |
| Dynamic Programming Approach | The complexity here is also O(n) time due to a single traversal of the string. Space complexity remains O(1) as no additional data structures are used beyond primitive types. |
| Two Pointers | — |
| Two Pointers (Optimization) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best general solution for substring constraints with limited violations |
| Dynamic Programming (Track Duplicate Pair Positions) | O(n) | O(1) | Useful when modeling the problem as state transitions while scanning the string |
2730. Find the Longest Semi-Repetitive Substring | LEETCODE BIWEEKLY 106 • code Explainer • 894 views views
Watch 9 more video solutions →Practice Find the Longest Semi-Repetitive Substring with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor