跳转至

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$ 的特殊子字符串也一定存在,这存在着单调性,因此我们可以使用二分查找的方法来找到最长的特殊子字符串。

我们定义二分查找的左边界 $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$。

时间复杂度 $O((n + |\Sigma|) \times \log n)$,空间复杂度 $O(|\Sigma|)$,其中 $n$ 是字符串 $s$ 的长度,而 $|\Sigma|$ 表示字符集的大小,本题中字符集为小写英文字母,因此 $|\Sigma| = 26$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
}

评论