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

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

题目描述

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

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

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

示例 1： 输入：s = "52233" 输出：4 解释： 最长的半重复子字符串是 "5223"。整个字符串 "52233" 有两个相邻的相同数字对22和33，但最多只能选取一个。 示例 2： 输入:s = "5494" 输出：4 解释： s 是一个半重复字符串。

解题思路

• 本题还是滑动窗口类型题目，关键词最长、子字符串的长度，而滑动窗口就是要确定左指针、右指针的所指位置、左右指针如何移动，以及是否需要辅助空间（记录元素出现次数、是否重复等）.
• 需要一个变量same，当right向右扩展时，如果s[right] == s[right - 1]，则same += 1。这里可以采用以下直观的形式：

    if s[right] == s[right - 1]:
        same += 1

• 我们也可以合并成一行代码，将[right] == s[right - 1]当成一个表达式，如果为真，则same += 1，否则same 不变：

    same += s[right] == s[right - 1]

• ans的初始值为1，因为至少有一个字符的子字符串是半重复的。
• right从1开始，因为s[0]本身就是一个半重复子字符串，left从0开始，因为左指针可以移动到0位置。判断right从那开始，就看最先开始遍历的位置之前的元素是否符合条件。同时对于本题，因为要判断相邻元素是否相等，所以right从1开始遍历。
• 在本题中我们不需要额外的空间记录元素出现的次数等，而左右指针的指向即为字串的看
• 当same > 1时，说明出现了两个相邻的相同字符，此时需要将左指针向右移动，直到s[left] == s[left - 1],此时移出两个相邻相等字符中的一个，same可以重置为1。

    if same > 1:
        if s[left] == s[left - 1]:
            same -= 1
        left += 1

• 当same > 1时，说明出现了两个相邻的相同字符，此时需要将左指针向右移动，直到s[left] == s[left - 1],此时移出两个相邻相等的字符，same可以重置为1。但是编程可以逆向思维，当s[left] != s[left - 1]时，一直移动left指针，直到s[left] == s[left - 1]，此时same重置为1。

    if same > 1:
        left += 1
        while s[left] != s[left - 1]:
            left += 1
        same = 1

• 最后，当每次判断玩left指针的移动后，更新答案ans，ans = max(ans, right - left + 1)。