[LeetCode] 2730. Find the Longest Semi-Repetitive Substring

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’

找到最长的半重复子字符串。

给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。

如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。例如，”0010” 、”002020” 、”0123” 、”2002” 和 “54944” 是半重复字符串，而 “00101022” （相邻的相同数字对是 00 和 22）和 “1101234883” （相邻的相同数字对是 11 和 88）不是半重复字符串。

请你返回 s 中最长 半重复子字符串的长度。

思路

这是一道可以用 76 题模板解决的滑动窗口题。思路没什么需要特别解释的，可直接参见代码。实现需要注意一个细节，就是怎么判断当前窗口是否是半重复的。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        int start = 0;
        int end = 0;
        int res = 0;
        int r = 0;
        while (end < s.length()) {
            char c1 = s.charAt(end);
            if (end > 0 && s.charAt(end - 1) == c1) {
                r++;
            }
            end++;
            while (r == 2) {
                char c2 = s.charAt(start);
                if (s.charAt(start + 1) == c2) {
                    r--;
                }
                start++;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }
}