Medium

题目描述

给你一个数字字符串 s，它由数字 0 到 9 组成。

如果一个字符串最多包含一对相邻的相同数字，则称为半重复字符串。例如，“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 是一个半重复字符串。

示例 3：

输入：s = "1111111"
输出：2
解释：最长的半重复子字符串是 "11"。选择子字符串 "111" 有两对相邻的相同数字，但最多只允许一对。

约束条件：

  • 1 <= s.length <= 50
  • '0' <= s[i] <= '9'

解题思路

解题思路

这道题要求找到最长的半重复子字符串，其中半重复是指最多只有一对相邻相同的数字。

方法一：暴力枚举（推荐） 由于字符串长度最多为50，我们可以枚举所有可能的子字符串，检查每个子字符串是否是半重复的。对于每个子字符串，统计相邻相同数字对的数量，如果数量不超过1，则更新最大长度。

方法二：滑动窗口 使用滑动窗口的思想，维护一个窗口，窗口内最多有一对相邻相同的数字。当遇到第二对相邻相同数字时，收缩窗口的左端点，直到窗口内只有一对相邻相同数字。

时间复杂度方面，由于字符串长度较小，暴力枚举的复杂度 O(n³) 是可以接受的，而滑动窗口的复杂度为 O(n)。考虑到代码实现的简洁性和题目规模，暴力枚举更适合。

实现时，对于每个子字符串，我们遍历一遍统计相邻相同数字对的数量，如果不超过1则更新答案。

代码实现

class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int n = s.length();
        int maxLen = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int pairs = 0;
                for (int k = i; k < j; k++) {
                    if (s[k] == s[k + 1]) {
                        pairs++;
                    }
                }
                if (pairs <= 1) {
                    maxLen = max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        n = len(s)
        max_len = 1
        
        for i in range(n):
            for j in range(i, n):
                pairs = 0
                for k in range(i, j):
                    if s[k] == s[k + 1]:
                        pairs += 1
                if pairs <= 1:
                    max_len = max(max_len, j - i + 1)
        
        return max_len

public class Solution {
    public int LongestSemiRepetitiveSubstring(string s) {
        int n = s.Length;
        int maxLen = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int pairs = 0;
                for (int k = i; k < j; k++) {
                    if (s[k] == s[k + 1]) {
                        pairs++;
                    }
                }
                if (pairs <= 1) {
                    maxLen = Math.Max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
}

var longestSemiRepetitiveSubstring = function(s) {
    let maxLen = 1;
    let left = 0;
    let pairCount = 0;
    
    for (let right = 1; right < s.length; right++) {
        if (s[right] === s[right - 1]) {
            pairCount++;
        }
        
        while (pairCount > 1) {
            if (s[left] === s[left + 1]) {
                pairCount--;
            }
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
暴力枚举O(n³)O(1)
滑动窗口O(n)O(1)

其中 n 为字符串长度。由于题目约束 n ≤ 50，暴力枚举的复杂度完全可以接受。