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

题目描述

给你一个字符串 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\) 的整段相同字符，且不能只是更长相同段的一部分。\(|s|\le 100\)，按段扫描即可。

若滑窗只看长度为 \(k\) 的窗口，两端同字符时会把更长段误判为合法。

双指针找出每一段连续相同字符，当且仅当段长恰好为 \(k\) 时返回真。

题目相当于要我们找出每一段连续的相同字符，然后判断是否存在一段长度为 \(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)\)。

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

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

题目描述

解法

方法一：双指针

评论