Teaching Kids Programming – Longer Contiguous Segments of Ones than Zeros in a Binary String (Three Algorithms)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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’.

Longer Contiguous Segments of Ones than Zeros in a Binary String

There are a few approaches to solve this problem.

Four variables – Single Pass

We can use four variables to track the current consecutive ones, current consecutive zeros, maximum consecutive ones, and maximum consecutive zeros. We need to perform a single pass linear scan to update these four variables. When we meet a ‘1’, we increment the current ones, and reset current zeros. When we meet a ‘0’, we increment the current zeros, and reset current ones. Each iteration, we check to see if the max consecutive ones or max consecutive zeros needs updating.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        zero = one = 0
        max0 = max1 = 0
        for i in s:
            if i == '1':
                one += 1
                zero = 0
            else:
                zero += 1
                one = 0
            max0 = max(max0, zero)
            max1 = max(max1, one)
        return max1 > max0

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        zero = one = 0
        max0 = max1 = 0
        for i in s:
            if i == '1':
                one += 1
                zero = 0
            else:
                zero += 1
                one = 0
            max0 = max(max0, zero)
            max1 = max(max1, one)
        return max1 > max0

The time complexity is O(N), and the space complexity is O(1) constant.

Using Split to Find out Contiguous Segments of Ones or Zeros

We can use the split function by either delimiter ‘0’ or ‘1’ into an array of contiguous segment of 1s or contiguous segment of 0s respectively. Then we can find out the maximum length of each string in the array.

1
2
3
4
5

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        ones = s.split('0')
        zeros = s.split('1')
        return max(len(i) for i in ones) > max(len(i) for i in zeros)        

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        ones = s.split('0')
        zeros = s.split('1')
        return max(len(i) for i in ones) > max(len(i) for i in zeros)        

This takes O(N) – however, requires four passes. The space complexity is O(N) – one array for 1’s, and one array for 0’s, and two temp arrays for checking the max length.

We can specify the key parameter as the len function so that the max function returns the longest segments, and this can be rewritten as:

1

return len(max(ones, key=len)) > len(max(zeros, key=len))

return len(max(ones, key=len)) > len(max(zeros, key=len))

Using GroupBy to Find out Contiguous Segments of Ones or Zeros

And we can use the itertools.groupby function to group into segments of 1’s and 0’s, then we can find out the length of each segments. The groupby returns the iterator to tuples of (key, value) where key is the element of each group, and the value points to the iterator to the corresponding group.

1
2
3
4
5
6
7
8
9

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        ones = zeros = 0
        for i, a in itertools.groupby(s):
            if i == '1':
                ones = max(ones, len(list(a)))
            else:
                zeros = max(zeros, len(list(a)))
        return ones > zeros

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        ones = zeros = 0
        for i, a in itertools.groupby(s):
            if i == '1':
                ones = max(ones, len(list(a)))
            else:
                zeros = max(zeros, len(list(a)))
        return ones > zeros

We can use a Counter aka Hash map to simplify the implementation, and make it concise.

1
2
3
4
5
6

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        c = Counter()
        for i, a in itertools.groupby(s):
            c[i] = max(c[i], len(list(a)))
        return c['1'] > c['0']

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        c = Counter()
        for i, a in itertools.groupby(s):
            c[i] = max(c[i], len(list(a)))
        return c['1'] > c['0']

Both implementations are O(N) time/space as the groupby function.

–EOF (The Ultimate Computing & Technology Blog) —