Question

1869. Longer Contiguous Segments of Ones than Zeros

中文文档

Description

Given a binary string s, return true_ if the longest contiguous segment of _1'_s is strictly longer than the longest contiguous segment of _0'_s in _s, or return false_ otherwise_.

• For example, in s = "110100010" the longest continuous segment of 1s has length 2, and the longest continuous segment of 0s has length 3.

Note that if there are no 0's, then the longest continuous segment of 0's is considered to have a length 0. The same applies if there is no 1's.

 

Example 1:

Input: s = "1101"
Output: true
Explanation:
The longest contiguous segment of 1s has length 2: "1101"
The longest contiguous segment of 0s has length 1: "1101"
The segment of 1s is longer, so return true.

Example 2:

Input: s = "111000"
Output: false
Explanation:
The longest contiguous segment of 1s has length 3: "111000"
The longest contiguous segment of 0s has length 3: "111000"
The segment of 1s is not longer, so return false.

Example 3:

Input: s = "110100010"
Output: false
Explanation:
The longest contiguous segment of 1s has length 2: "110100010"
The longest contiguous segment of 0s has length 3: "110100010"
The segment of 1s is not longer, so return false.

 

Constraints:

• 1 <= s.length <= 100
• s[i] is either '0' or '1'.

Solutions

Solution 1: Two Passes

We design a function $f(x)$, which represents the length of the longest consecutive substring in string $s$ composed of $x$. If $f(1) > f(0)$, then return true, otherwise return false.

The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)`.

class Solution:
  def checkZeroOnes(self, s: str) -> bool:
    def f(x: str) -> int:
      cnt = mx = 0
      for c in s:
        if c == x:
          cnt += 1
          mx = max(mx, cnt)
        else:
          cnt = 0
      return mx

    return f("1") > f("0")

class Solution {
  public boolean checkZeroOnes(String s) {
    return f(s, '1') > f(s, '0');
  }

  private int f(String s, char x) {
    int cnt = 0, mx = 0;
    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == x) {
        mx = Math.max(mx, ++cnt);
      } else {
        cnt = 0;
      }
    }
    return mx;
  }
}

class Solution {
public:
  bool checkZeroOnes(string s) {
    auto f = [&](char x) {
      int cnt = 0, mx = 0;
      for (char& c : s) {
        if (c == x) {
          mx = max(mx, ++cnt);
        } else {
          cnt = 0;
        }
      }
      return mx;
    };
    return f('1') > f('0');
  }
};

func checkZeroOnes(s string) bool {
  f := func(x rune) int {
    cnt, mx := 0, 0
    for _, c := range s {
      if c == x {
        cnt++
        mx = max(mx, cnt)
      } else {
        cnt = 0
      }
    }
    return mx
  }
  return f('1') > f('0')
}

function checkZeroOnes(s: string): boolean {
  const f = (x: string): number => {
    let [mx, cnt] = [0, 0];
    for (const c of s) {
      if (c === x) {
        mx = Math.max(mx, ++cnt);
      } else {
        cnt = 0;
      }
    }
    return mx;
  };
  return f('1') > f('0');
}

/**
 * @param {string} s
 * @return {boolean}
 */
var checkZeroOnes = function (s) {
  const f = x => {
    let [mx, cnt] = [0, 0];
    for (const c of s) {
      if (c === x) {
        mx = Math.max(mx, ++cnt);
      } else {
        cnt = 0;
      }
    }
    return mx;
  };
  return f('1') > f('0');
};