Find the Longest Semi-Repetitive Substring
MedPrompt
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'
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to generate every possible substring of the input string s, check each one to see if it's semi-repetitive, and keep track of the longest valid one found.
Algorithm
- Initialize
maxLengthto 0. - Use two nested loops with indices
iandjto generate all substrings. - For each substring, create a helper function
isSemiRepetitiveto check its validity. - Inside the helper function, count the number of adjacent identical characters.
- If the count is at most 1, the substring is valid.
- If valid, update
maxLengthwith the current substring's length if it's greater. - Return
maxLengthafter checking all substrings.
Walkthrough
This method systematically checks all substrings. A substring is defined by its start and end indices. We can use two nested loops to iterate through all possible start and end points. For each generated substring, a helper function is called to determine if it's semi-repetitive.
A string is semi-repetitive if it contains at most one pair of adjacent identical digits. The helper function isSemiRepetitive iterates through the substring and counts these pairs. If the count exceeds one, the substring is invalid. Otherwise, it's valid, and we compare its length with our current maximum.
class Solution { private boolean isSemiRepetitive(String s) { int pairs = 0; for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) == s.charAt(i + 1)) { pairs++; } } return pairs <= 1; } public int longestSemiRepetitiveSubstring(String s) { int n = s.length(); int maxLength = 0; if (n > 0) { maxLength = 1; } for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { String sub = s.substring(i, j + 1); if (isSemiRepetitive(sub)) { maxLength = Math.max(maxLength, sub.length()); } } } return maxLength; }}Complexity
Time
O(n^3), where n is the length of the string `s`. Generating all substrings takes O(n^2) iterations. For each substring, checking if it's semi-repetitive takes up to O(n) time. This leads to a cubic time complexity.
Space
O(n) in the worst case, due to the space required to store the substring being checked. `s.substring()` can create a new string of length up to n.
Trade-offs
Pros
Very simple to conceptualize and implement.
Guaranteed to be correct.
Cons
Highly inefficient due to its O(n^3) time complexity.
Not suitable for larger input sizes (though it passes for n <= 50).
This approach improves on the naive brute-force method by optimizing the check for the semi-repetitive property. Instead of re-evaluating each substring from scratch, we extend a substring one character at a time and maintain a running count of adjacent pairs.
Algorithm
- Initialize
maxLengthto 1. - Use an outer loop
ito iterate through all possible start indices. - For each
i, initializeadjacentPairs = 0. - Use an inner loop
jto extend the substring fromi. - As
jincreases, updateadjacentPairsifs[j] == s[j-1]. - If
adjacentPairsbecomes greater than 1, break the inner loop. - Otherwise, update
maxLengthwith the current valid substring's length. - Return
maxLength.
Walkthrough
We still use two nested loops to define our substrings. The outer loop fixes the starting point i, and the inner loop extends the substring by moving the endpoint j. For a fixed i, as we increment j, we only need to check the newly added character s[j] against its predecessor s[j-1].
We keep a count of adjacent pairs for the current substring s[i...j]. If this count ever exceeds 1, we know that this substring and any longer one starting at i will also be invalid. This allows us to break the inner loop early and move to the next starting position i, avoiding unnecessary computations.
class Solution { public int longestSemiRepetitiveSubstring(String s) { int n = s.length(); if (n <= 1) { return n; } int maxLength = 1; for (int i = 0; i < n; i++) { int adjacentPairs = 0; for (int j = i + 1; j < n; j++) { if (s.charAt(j) == s.charAt(j - 1)) { adjacentPairs++; } if (adjacentPairs <= 1) { maxLength = Math.max(maxLength, j - i + 1); } else { break; } } } return maxLength; }}Complexity
Time
O(n^2). We have two nested loops, and the work inside the inner loop is constant time.
Space
O(1), as we only use a few variables to store the state (`maxLength`, `adjacentPairs`, loop indices).
Trade-offs
Pros
A significant improvement over the O(n^3) approach.
Still relatively easy to understand.
Cons
Not the most optimal solution; can be improved to linear time.
The most efficient solution utilizes the sliding window pattern. We maintain a 'window' (a substring) that is always semi-repetitive. We expand the window by moving its right boundary. If the window becomes invalid (more than one pair), we shrink it from the left until it's valid again, ensuring we only traverse the string once.
Algorithm
- Initialize pointers
left = 0,right = 0, and a variablelastPairIndex = -1. - Iterate
rightfrom 1 ton-1. - If
s[right] == s[right-1], a pair is found. - If this is the second pair in the window (i.e.,
lastPairIndex != -1), shrink the window by settingleft = lastPairIndex. - Update
lastPairIndexto the current pair's position (right). - In each iteration, update
maxLengthwith the size of the current valid window (right - left + 1). - Return
maxLength.
Walkthrough
This approach uses two pointers, left and right, to define the current window s[left...right]. The right pointer always moves forward to expand the window. The left pointer only moves forward when the window needs to be shrunk.
To efficiently track the validity of the window, we only need to remember the position of the first adjacent pair we encounter. Let's say we store the index of the second character of this pair in lastPairIndex. When we find a new pair at right, if lastPairIndex is already set, it means we've found a second pair. To make the window valid again, we must slide the left pointer to the position of that first pair. We then update lastPairIndex to the position of the new pair. At each step, we calculate the length of the current valid window and update our overall maximum length.
class Solution { public int longestSemiRepetitiveSubstring(String s) { int n = s.length(); if (n <= 2) { return n; } int maxLength = 1; int left = 0; // Stores the index of the second character of the first pair in the current window int lastPairIndex = -1; for (int right = 1; right < n; right++) { if (s.charAt(right) == s.charAt(right - 1)) { if (lastPairIndex != -1) { // This is the second pair, shrink the window left = lastPairIndex; } // Record the position of the current pair lastPairIndex = right; } maxLength = Math.max(maxLength, right - left + 1); } return maxLength; }}Complexity
Time
O(n). Both the `left` and `right` pointers traverse the string at most once, resulting in a linear time complexity.
Space
O(1). We only use a few variables to keep track of pointers and the maximum length, regardless of the input size.
Trade-offs
Pros
Optimal time complexity.
Efficient for any input size.
Cons
The logic can be slightly more complex to devise compared to brute-force methods.
Solutions
Solution
class Solution {public int longestSemiRepetitiveSubstring(String s) { int n = s.length(); int ans = 0; for (int i = 0, j = 0, cnt = 0; i < n; ++i) { if (i > 0 && s.charAt(i) == s.charAt(i - 1)) { ++cnt; } while (cnt > 1) { if (s.charAt(j) == s.charAt(j + 1)) { --cnt; } ++j; } ans = Math.max(ans, i - j + 1); } return ans; }}class Solution {public: int longestSemiRepetitiveSubstring(string s) { int n = s.size(); int ans = 0; for (int i = 0, j = 0, cnt = 0; i < n; ++i) { if (i && s[i] == s[i - 1]) { ++cnt; } while (cnt > 1) { if (s[j] == s[j + 1]) { --cnt; } ++j; } ans = max(ans, i - j + 1); } return ans; }};class Solution: def longestSemiRepetitiveSubstring(self, s: str) -> int: n = len(s) ans = cnt = j = 0 for i in range(n): if i and s[i] == s[i - 1]: cnt += 1 while cnt > 1: if s[j] == s[j + 1]: cnt -= 1 j += 1 ans = max(ans, i - j + 1) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.