1869-哪种连续子字符串更长

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长
连续子字符串，返回 true ；否则，返回 false __ 。

  • 例如，s = " **11** 01 **000** 10" 中，由 1 组成的最长连续子字符串的长度是 2 ，由 0 组成的最长连续子字符串的长度是 3 。

注意，如果字符串中不存在 0 ，此时认为由 0 组成的最长连续子字符串的长度是 0 。字符串中不存在 1 的情况也适用此规则。

示例 1：

**输入：** s = "1101"
**输出：** true
**解释：**
由 1 组成的最长连续子字符串的长度是 2：" **11** 01"
由 0 组成的最长连续子字符串的长度是 1："11 **0** 1"
由 1 组成的子字符串更长，故返回 true 。

示例 2：

**输入：** s = "111000"
**输出：** false
**解释：**
由 1 组成的最长连续子字符串的长度是 3：" **111** 000"
由 0 组成的最长连续子字符串的长度是 3："111 **000** "
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。

示例 3：

**输入：** s = "110100010"
**输出：** false
**解释：**
由 1 组成的最长连续子字符串的长度是 2：" **11** 0100010"
由 0 组成的最长连续子字符串的长度是 3："1101 **000** 10"
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。

提示：

  • 1 <= s.length <= 100
  • s[i] 不是 '0' 就是 '1'

方法一：遍历字符串

思路与算法

我们可以遍历字符串并维护连续的 0' 与 1’ 子串的最长长度 mx}_0 与 mx}_1。

在遍历字符串的时候，我们维护上一个字符 prev 与当前连续子串的最长长度 cnt。

对于每一个字符 ch，我们判断它与 prev 是否相等：

  • 如果相等，则将 cnt 增加 1；

  • 如果不相等，则根据 prev 的内容更新对应的 mx}_0 与 mx}_1。

除此以外，在遍历结束后，我们还需要根据字符串结尾的连续子串形式维护对应的 mx}_0 与 mx}_1。

最终，我们比较 mx}_0 与 mx}_1 的大小并返回答案。

代码

[sol1-C++]
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
class Solution {
public:
    bool checkZeroOnes(string s) {
        int mx0 = 0;
        int mx1 = 0;
        char prev = '#';   // 上个字符
        int cnt = 0;
        for (char ch: s){
            // 当前字符与上个字符相等
            if (ch == prev){
                ++cnt;
            }
            // 当前字符与上个字符不相等
            else{
                if (prev == '0'){
                    mx0 = max(mx0, cnt);
                }
                else if (prev == '1'){
                    mx1 = max(mx1, cnt);
                }
                cnt = 1;
            }
            prev = ch;
        }
        // 字符串结尾的连续子串
        if (prev == '0'){
            mx0 = max(mx0, cnt);
        }
        else if (prev == '1'){
            mx1 = max(mx1, cnt);
        }
        return mx1 > mx0;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        mx0, mx1 = 0, 0
        cnt = 0
        prev = '#'   # 上个字符
        for ch in s:
            # 当前字符与上个字符相等
            if prev == ch:
                cnt += 1
            # 当前字符与上个字符不相等
            else:
                if prev == '0':
                    mx0 = max(mx0, cnt)
                elif prev == '1':
                    mx1 = max(mx1, cnt)
                cnt = 1
            prev = ch
        # 字符串结尾的连续子串
        if prev == '0':
            mx0 = max(mx0, cnt)
        elif prev == '1':
            mx1 = max(mx1, cnt)
        return mx1 > mx0

复杂度分析

  • 时间复杂度：O(n)，其中 n 为字符串的长度，即为遍历一遍字符串的时间复杂度。

  • 空间复杂度：O(1)，我们只使用了常数个变量。

 Comments
On this page
1869-哪种连续子字符串更长