哪种连续子字符串更长

标签: 字符串

难度: Easy

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

Submission

运行时间: 18 ms

内存: 15.9 MB

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        max_zeros, max_ones = 0, 0
        slow, fast, n = 0, 0, len(s)
        while fast < n:
            if s[slow] == s[fast]:
                if s[slow] == "0":
                    max_zeros = max(max_zeros, fast - slow + 1)
                else:
                    max_ones = max(max_ones, fast - slow + 1)
            else:
                slow = fast
                fast -= 1
            fast += 1
        return max_ones > max_zeros

Explain

此题解通过滑动窗口的方法，遍历字符串来计算由'0'和'1'组成的最长连续子字符串的长度。首先定义两个变量max_zeros和max_ones来分别存储最长的0串和1串的长度。使用两个指针slow和fast来定义当前考察的子串的起始和结束位置，并通过遍历整个字符串来更新这两个最大值。当遇到当前字符与起始字符相同时，根据是'0'还是'1'，更新max_zeros或max_ones。如果当前字符与起始字符不同，则将slow指针移动到fast的位置，这样可以开始新的子串的计数。最后，比较max_ones和max_zeros的值，如果由'1'组成的子字符串长度严格大于由'0'组成的，返回true，否则返回false。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        max_zeros, max_ones = 0, 0  # 初始化0和1的最长连续子串长度
        slow, fast, n = 0, 0, len(s)  # 初始化双指针以及字符串长度
        while fast < n:  # 遍历字符串
            if s[slow] == s[fast]:  # 当前区间字符相同
                if s[slow] == '0':
                    max_zeros = max(max_zeros, fast - slow + 1)  # 更新0的最长长度
                else:
                    max_ones = max(max_ones, fast - slow + 1)  # 更新1的最长长度
            else:
                slow = fast  # 发现不同字符，移动slow到当前fast的位置
                fast -= 1  # 调整fast，准备下一次循环
            fast += 1  # 移动fast指针
        return max_ones > max_zeros  # 判断1的最长串是否大于0的最长串

Explore

滑动窗口方法与一次遍历统计其实在本题中大体相似，主要区别在于语义表达。滑动窗口通常用于动态调整窗口大小以寻找最优解，在处理变长子数组或子串问题时尤为有效。在此题中，使用滑动窗口可以清晰地展现出窗口的移动和调整过程，即便其本质上与一次遍历统计相同。这种方法提供了更好的可读性和易于理解的逻辑流程，特别是在处理更复杂的变长子串问题时，滑动窗口的框架可以直接应用，提高代码的复用性。

题解中的算法确实没有直接在循环结束时处理末尾的连续子字符串，这可能导致如果最长的连续子字符串恰好在字符串的末尾时，其长度不会被正确更新。为了解决这个问题，可以在循环结束后再进行一次长度更新操作，检查并更新最后一个子字符串的长度。这样可以确保无论连续子字符串是否在末尾，都能被正确计算。

确实，题解中对指针的处理略显复杂和多余。更简洁的方法是在发现不同字符时，直接将slow指针设置为fast，而不需要对fast指针进行减1再加1的操作。这样不仅简化了代码，也提高了其执行效率，因为避免了不必要的指针操作。

题解中的算法在输入字符串全为‘0’或全为‘1’时，将会正确地更新max_zeros或max_ones的值，因为整个字符串会被视为一个连续子字符串。然而，需要注意的是，如果字符串全为‘0’，则max_ones将保持为0，反之亦然。这在逻辑上是正确的，但应在实际应用中根据具体需求判断是否需要对全0或全1的情况做特殊处理或输出说明。