Easy

题目描述

给你一个字符串 s 和一个整数 k。

判断是否存在一个长度恰好为 k 的子串，满足以下条件：

  • 子串只由一个不同的字符组成（例如，“aaa” 或 “bbb”）。
  • 如果子串前面有字符，该字符必须与子串中的字符不同。
  • 如果子串后面有字符，该字符也必须与子串中的字符不同。

如果存在这样的子串，返回 true。否则，返回 false。

示例 1：

输入：s = "aaabaaa", k = 3
输出：true
解释：
子串 s[4..6] == "aaa" 满足条件。
- 长度为 3。
- 所有字符都相同。
- "aaa" 前面的字符是 'b'，与 'a' 不同。
- "aaa" 后面没有字符。

示例 2：

输入：s = "abc", k = 2
输出：false
解释：
不存在长度为 2 的子串，由一个不同字符组成且满足条件。

提示：

  • 1 <= k <= s.length <= 100
  • s 只由小写英文字母组成

解题思路

这道题要求找到一个长度为 k 的特殊子串，需要同时满足三个条件：

  1. 子串由相同字符组成
  2. 前一个字符（如果存在）与子串字符不同
  3. 后一个字符（如果存在）与子串字符不同

解法一：滑动窗口法（推荐） 使用固定长度为 k 的滑动窗口遍历字符串。对于每个窗口，检查是否所有字符都相同，以及边界条件是否满足。

解法二：暴力枚举法 对每个可能的起始位置，检查从该位置开始长度为 k 的子串是否满足条件。

两种解法的时间复杂度都是 O(n×k)，但滑动窗口法在实现上更清晰。由于题目约束较小（n ≤ 100），两种方法都能高效解决。

具体实现时，我们遍历所有可能的起始位置 i（从 0 到 n-k），对每个位置：

  1. 检查 s[i] 到 s[i+k-1] 是否都相等
  2. 检查前一个字符 s[i-1]（如果存在）是否与当前字符不同
  3. 检查后一个字符 s[i+k]（如果存在）是否与当前字符不同

如果找到满足条件的子串，立即返回 true；遍历完所有位置后仍未找到，则返回 false。

代码实现

class Solution {
public:
    bool hasSpecialSubstring(string s, int k) {
        int n = s.length();
        
        for (int i = 0; i <= n - k; i++) {
            // 检查子串是否由相同字符组成
            bool allSame = true;
            for (int j = i + 1; j < i + k; j++) {
                if (s[j] != s[i]) {
                    allSame = false;
                    break;
                }
            }
            
            if (!allSame) continue;
            
            // 检查前一个字符
            if (i > 0 && s[i - 1] == s[i]) continue;
            
            // 检查后一个字符
            if (i + k < n && s[i + k] == s[i]) continue;
            
            return true;
        }
        
        return false;
    }
};

class Solution:
    def hasSpecialSubstring(self, s: str, k: int) -> bool:
        n = len(s)
        
        for i in range(n - k + 1):
            # 检查子串是否由相同字符组成
            if not all(s[j] == s[i] for j in range(i, i + k)):
                continue
            
            # 检查前一个字符
            if i > 0 and s[i - 1] == s[i]:
                continue
            
            # 检查后一个字符
            if i + k < n and s[i + k] == s[i]:
                continue
            
            return True
        
        return False

public class Solution {
    public bool HasSpecialSubstring(string s, int k) {
        int n = s.Length;
        
        for (int i = 0; i <= n - k; i++) {
            // 检查子串是否由相同字符组成
            bool allSame = true;
            for (int j = i + 1; j < i + k; j++) {
                if (s[j] != s[i]) {
                    allSame = false;
                    break;
                }
            }
            
            if (!allSame) continue;
            
            // 检查前一个字符
            if (i > 0 && s[i - 1] == s[i]) continue;
            
            // 检查后一个字符
            if (i + k < n && s[i + k] == s[i]) continue;
            
            return true;
        }
        
        return false;
    }
}

var hasSpecialSubstring = function(s, k) {
    const n = s.length;
    
    for (let i = 0; i <= n - k; i++) {
        // 检查子串是否由相同字符组成
        let allSame = true;
        for (let j = i + 1; j < i + k; j++) {
            if (s[j] !== s[i]) {
                allSame = false;
                break;
            }
        }
        
        if (!allSame) continue;
        
        // 检查前一个字符
        if (i > 0 && s[i - 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n × k)
空间复杂度O(1)

其中 n 是字符串长度。在最坏情况下，需要检查 n-k+1 个起始位置，每个位置需要 O(k) 时间验证子串是否由相同字符组成。