README.md

comments	difficulty	edit_url	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/3400-3499/3456.Find%20Special%20Substring%20of%20Length%20K/README.md	字符串

3456. 找出长度为 K 的特殊子字符串

English Version

题目描述

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

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

1. 该子字符串 只包含一个唯一字符（例如，"aaa" 或 "bbb"）。
2. 如果该子字符串的 前面 有字符，则该字符必须与子字符串中的字符不同。
3. 如果该子字符串的 后面 有字符，则该字符也必须与子字符串中的字符不同。

如果存在这样的子串，返回 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$ 的子字符串，若存在则返回 $\textit{true}$，否则返回 $\textit{false}$。

我们可以用双指针 $l$ 和 $r$ 来遍历字符串 $s$，当 $s[l] = s[r]$ 时，$r$ 向右移动，直到 $s[r] \neq s[l]$，此时判断 $r - l$ 是否等于 $k$，若等于则返回 $\textit{true}$，否则 $l$ 移动到 $r$ 继续遍历。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def hasSpecialSubstring(self, s: str, k: int) -> bool:
        l, n = 0, len(s)
        while l < n:
            r = l
            while r < n and s[r] == s[l]:
                r += 1
            if r - l == k:
                return True
            l = r
        return False

Java

class Solution {
    public boolean hasSpecialSubstring(String s, int k) {
        int n = s.length();
        for (int l = 0, cnt = 0; l < n;) {
            int r = l + 1;
            while (r < n && s.charAt(r) == s.charAt(l)) {
                ++r;
            }
            if (r - l == k) {
                return true;
            }
            l = r;
        }
        return false;
    }
}

C++

class Solution {
public:
    bool hasSpecialSubstring(string s, int k) {
        int n = s.length();
        for (int l = 0, cnt = 0; l < n;) {
            int r = l + 1;
            while (r < n && s[r] == s[l]) {
                ++r;
            }
            if (r - l == k) {
                return true;
            }
            l = r;
        }
        return false;
    }
};

Go

func hasSpecialSubstring(s string, k int) bool {
	n := len(s)
	for l := 0; l < n; {
		r := l + 1
		for r < n && s[r] == s[l] {
			r++
		}
		if r-l == k {
			return true
		}
		l = r
	}
	return false
}

TypeScript

function hasSpecialSubstring(s: string, k: number): boolean {
    const n = s.length;
    for (let l = 0; l < n; ) {
        let r = l + 1;
        while (r < n && s[r] === s[l]) {
            r++;
        }
        if (r - l === k) {
            return true;
        }
        l = r;
    }
    return false;
}