Find the Longest Semi-Repetitive Substring — Solution
Find the Longest Semi-Repetitive Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Longest Semi-Repetitive Substring is a medium coding problem on strings and sliding window, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of digits. A string is semi-repetitive if it contains at most one pair of adjacent equal characters. For example "0010", "2026" and "54944" are semi-repetitive, while "00101022" (two pairs) and "1101234883" (two pairs) are not.
Return the length of the longest semi-repetitive substring of s.
Example 1
Input: s = "11233"
Output: 4
Explanation: The whole string has two adjacent pairs (`11` and `33`); `"1123"` and `"1233"` keep just one.
Example 2
Input: s = "2026"
Output: 4
Explanation: No adjacent pair at all.
Example 3
Input: s = "1111"
Output: 2
Constraints
1 <= s.length <= 50'0' <= s[i] <= '9'
Hints for Find the Longest Semi-Repetitive Substring
Hint 1
Think of a window
[l, r]and the number of positionsiin it withs[i] == s[i + 1].Hint 2
Growing the window to the right can add a pair; shrinking from the left can remove one.
Hint 3
Sliding window: extend
r, and while the window holds two pairs, advancel(dropping the pair atlwhens[l] == s[l + 1]). Track the longest window.
How to solve Find the Longest Semi-Repetitive Substring
A sliding window that keeps at most one adjacent equal pair inside; the longest window seen is the answer.
Approach
- Set
l = 0,pairs = 0,best = 1. - For each
rfrom 1 ton - 1: ifs[r] == s[r - 1], increasepairs. - While
pairs > 1: ifs[l] == s[l + 1], decreasepairs; then increasel. - Update
best = max(best, r - l + 1).
Why it works
pairs always counts the adjacent equal pairs fully inside [l, r]: a new pair enters when r advances onto a repeat, and the pair (l, l + 1) leaves when l advances past it. For each r, the loop moves l to the smallest index that keeps the window valid, so [l, r] is the longest semi-repetitive substring ending at r; validity is monotone (shrinking never adds pairs), which makes the two-pointer sweep correct.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- A string of length 1 is semi-repetitive; start
bestat 1. - When shrinking, check the pair
(l, l + 1)before movingl. - Pairs may overlap:
"111"already holds two of them, so it is not semi-repetitive.
Reference solution
Python
def longestSemiRepetitiveSubstring(s: str) -> int:
l = 0
pairs = 0
best = 1
for r in range(1, len(s)):
if s[r] == s[r - 1]:
pairs += 1
while pairs > 1:
if s[l] == s[l + 1]:
pairs -= 1
l += 1
best = max(best, r - l + 1)
return bestJava
public static int longestSemiRepetitiveSubstring(String s) {
int l = 0, pairs = 0, best = 1;
for (int r = 1; r < s.length(); r++) {
if (s.charAt(r) == s.charAt(r - 1)) pairs++;
while (pairs > 1) {
if (s.charAt(l) == s.charAt(l + 1)) pairs--;
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
}C++
int longestSemiRepetitiveSubstring(string s) {
int l = 0, pairs = 0, best = 1;
for (int r = 1; r < (int)s.size(); r++) {
if (s[r] == s[r - 1]) pairs++;
while (pairs > 1) {
if (s[l] == s[l + 1]) pairs--;
l++;
}
best = max(best, r - l + 1);
}
return best;
}JavaScript
var longestSemiRepetitiveSubstring = function(s) {
var l = 0, pairs = 0, best = 1;
for (var r = 1; r < s.length; r++) {
if (s[r] === s[r - 1]) pairs++;
while (pairs > 1) {
if (s[l] === s[l + 1]) pairs--;
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Sliding Window Technique