2730. Find the Longest Semi-Repetitive Substring
Description
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'
Solutions
Solution 1: Two Pointers
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)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
Solution 2: Two Pointers (Optimization)
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)$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|