题目描述
给你一个二进制字符串 s
。如果字符串中由 1
组成的 最长 连续子字符串 严格长于 由 0
组成的 最长 连续子字符串,返回 true
;否则,返回 false
。
例如,s = "110100010"
中,由 1
组成的最长连续子字符串的长度是 2
,由 0
组成的最长连续子字符串的长度是 3
。
注意,如果字符串中不存在 0
,此时认为由 0
组成的最长连续子字符串的长度是 0
。字符串中不存在 1
的情况也适用此规则。
样例
输入:s = "1101"
输出:true
解释:
由 1 组成的最长连续子字符串的长度是 2:"1101"
由 0 组成的最长连续子字符串的长度是 1:"1101"
由 1 组成的子字符串更长,故返回 true。
输入:s = "111000"
输出:false
解释:
由 1 组成的最长连续子字符串的长度是 3:"111000"
由 0 组成的最长连续子字符串的长度是 3:"111000"
由 1 组成的子字符串不比由 0 组成的子字符串长,故返回 false。
输入:s = "110100010"
输出:false
解释:
由 1 组成的最长连续子字符串的长度是 2:"110100010"
由 0 组成的最长连续子字符串的长度是 3:"110100010"
由 1 组成的子字符串不比由 0 组成的子字符串长,故返回 false。
限制
1 <= s.length <= 100
s[i]
不是'0'
就是'1'
。
算法
(模拟) $O(n)$
- 按照题目描述模拟,在
01
交替的时候统计最长连续子串。
时间复杂度
- 遍历字符串一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
bool checkZeroOnes(string s) {
const int n = s.size();
vector<int> res(2, 0);
vector<int> cnt(2, 0);
cnt[s[0] - '0']++;
for (int i = 1; i <= n; i++) {
if (i < n && s[i] == s[i - 1]) {
cnt[s[i] - '0']++;
} else {
int c = s[i - 1] - '0';
res[c] = max(res[c], cnt[c]);
cnt[c] = 0;
cnt[c ^ 1] = 1;
}
}
return res[1] > res[0];
}
};