2981. 找出出现至少三次的最长特殊子字符串 I

题目描述

给你一个仅由小写英文字母组成的字符串 s 。

如果一个字符串仅由单一字符组成，那么它被称为特殊字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。

返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。

子字符串 是字符串中的一个连续非空字符序列。

示例 1：

输入：s = "aaaa"
输出：2
解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
可以证明最大长度是 2 。

示例 2：

输入：s = "abcdef"
输出：-1
解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。

示例 3：

输入：s = "abcaba"
输出：1
解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
可以证明最大长度是 1 。

提示：

3 <= s.length <= 50
s 仅由小写英文字母组成。

解法

方法一：二分查找 + 滑动窗口计数

思考

特殊子串由同一字符组成。长度 \(x\) 可行则 \(x-1\) 也可行，故二分 \(x\)。一段连续相同字符长度为 \(L\) 时，其中长为 \(x\) 的子串有 \(\max(0, L-x+1)\) 个，按字符累加后看是否达到 \(3\)。

\(n \le 50\)，二分再线性计数即可。

我们注意到，如果一个长度为 \(x\) 且出现至少三次的特殊子字符串存在，那么长度为 \(x-1\) 的特殊子字符串也一定存在，这存在着单调性，因此我们可以使用二分查找的方法来找到最长的特殊子字符串。

我们定义二分查找的左边界 \(l = 0\)，右边界 \(r = n\)，其中 \(n\) 是字符串的长度。每次二分查找的过程中，我们取 \(mid = \lfloor \frac{l + r + 1}{2} \rfloor\)，如果长度为 \(mid\) 的特殊子字符串存在，那么我们就将左边界更新为 \(mid\)，否则我们就将右边界更新为 \(mid - 1\)。在二分查找的过程中，我们使用滑动窗口来计算特殊子字符串的个数。

具体地，我们设计一个函数 \(check(x)\)，表示长度为 \(x\) 且出现至少三次的特殊子字符串是否存在。

在函数 \(check(x)\) 中，我们定义一个哈希表或长度为 \(26\) 的数组 \(cnt\)，其中 \(cnt[i]\) 表示长度为 \(x\)，且由第 \(i\) 个小写字母组成的特殊子字符串的个数。我们遍历字符串 \(s\)，如果当前遍历到的字符为 \(s[i]\)，那么我们将指针 \(j\) 向右移动，直到 \(s[j] \neq s[i]\)，此时 \(s[i \cdots j-1]\) 就是一个长度为 \(x\) 的特殊子字符串，我们将 \(cnt[s[i]]\) 增加 \(\max(0, j - i - x + 1)\)，然后将指针 \(i\) 更新为 \(j\)。

在遍历结束之后，我们遍历数组 \(cnt\)，如果存在 \(cnt[i] \geq 3\)，那么就说明长度为 \(x\) 且出现至少三次的特殊子字符串存在，我们返回 \(true\)，否则返回 \(false\)。

Python3JavaC++GoTypeScript

class Solution:
    def maximumLength(self, s: str) -> int:
        def check(x: int) -> bool:
            cnt = defaultdict(int)
            i = 0
            while i < n:
                j = i + 1
                while j < n and s[j] == s[i]:
                    j += 1
                cnt[s[i]] += max(0, j - i - x + 1)
                i = j
            return max(cnt.values()) >= 3

        n = len(s)
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return -1 if l == 0 else l

class Solution {
    private String s;
    private int n;

    public int maximumLength(String s) {
        this.s = s;
        n = s.length();
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l == 0 ? -1 : l;
    }

    private boolean check(int x) {
        int[] cnt = new int[26];
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            int k = s.charAt(i) - 'a';
            cnt[k] += Math.max(0, j - i - x + 1);
            if (cnt[k] >= 3) {
                return true;
            }
            i = j;
        }
        return false;
    }
}

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size();
        int l = 0, r = n;
        auto check = [&](int x) {
            int cnt[26]{};
            for (int i = 0; i < n;) {
                int j = i + 1;
                while (j < n && s[j] == s[i]) {
                    ++j;
                }
                int k = s[i] - 'a';
                cnt[k] += max(0, j - i - x + 1);
                if (cnt[k] >= 3) {
                    return true;
                }
                i = j;
            }
            return false;
        };
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l == 0 ? -1 : l;
    }
};

func maximumLength(s string) int {
    n := len(s)
    l, r := 0, n
    check := func(x int) bool {
        cnt := [26]int{}
        for i := 0; i < n; {
            j := i + 1
            for j < n && s[j] == s[i] {
                j++
            }
            k := s[i] - 'a'
            cnt[k] += max(0, j-i-x+1)
            if cnt[k] >= 3 {
                return true
            }
            i = j
        }
        return false
    }
    for l < r {
        mid := (l + r + 1) >> 1
        if check(mid) {
            l = mid
        } else {
            r = mid - 1
        }
    }
    if l == 0 {
        return -1
    }
    return l
}

function maximumLength(s: string): number {
    const n = s.length;
    let [l, r] = [0, n];
    const check = (x: number): boolean => {
        const cnt: number[] = Array(26).fill(0);
        for (let i = 0; i < n;) {
            let j = i + 1;
            while (j < n && s[j] === s[i]) {
                j++;
            }
            const k = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
            cnt[k] += Math.max(0, j - i - x + 1);
            if (cnt[k] >= 3) {
                return true;
            }
            i = j;
        }
        return false;
    };
    while (l < r) {
        const mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l === 0 ? -1 : l;
}

方法二：计数

思考

方法一多次扫描整串。\(n\) 很小时也可对每段 run 把长度为 \(1 \ldots L\) 的特殊串出现次数直接加进哈希表：长 \(j\) 的串在该 run 中出现 \(L-j+1\) 次。最后取出现次数 \(\ge 3\) 的最大长度。

与二分相比少了对数轮，但仍是按 run 做贡献，适合本题的短串。

时间复杂度 \(O(n)\)。

TypeScript

function maximumLength(s: string): number {
    const cnt = new Map<string, number>();
    const n = s.length;
    let [c, ch] = [0, ''];

    for (let i = 0; i < n + 1; i++) {
        if (ch === s[i]) {
            c++;
        } else {
            let j = 1;
            while (c) {
                const char = ch.repeat(j++);
                cnt.set(char, (cnt.get(char) ?? 0) + c);
                c--;
            }

            ch = s[i];
            c = 1;
        }
    }

    let res = -1;
    for (const [x, c] of cnt) {
        if (c >= 3) {
            res = Math.max(res, x.length);
        }
    }

    return res;
}

2981. 找出出现至少三次的最长特殊子字符串 I

题目描述

解法

方法一：二分查找 + 滑动窗口计数

方法二：计数

评论