Skip to content

Latest commit

 

History

History
110 lines (92 loc) · 3.65 KB

README.md

File metadata and controls

110 lines (92 loc) · 3.65 KB

Given a binary string s, return true if the longest contiguous segment of 1s is strictly longer than the longest contiguous segment of 0s in s. Return false otherwise.

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

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

 

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

Related Topics:
Array, Two Pointers

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/longer-contiguous-segments-of-ones-than-zeros/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    int longest(string s, char c) {
        int ans = 0;
        for (int i = 0; i < s.size(); ) {
            if (s[i] != c) ++i;
            else {
                int start = i;
                while (i < s.size() && s[i] == c) ++i;
                ans = max(ans, i - start);
            }
        }
        return ans;
    }
public:
    bool checkZeroOnes(string s) {
        return longest(s, '0') < longest(s, '1');
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/longer-contiguous-segments-of-ones-than-zeros/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool checkZeroOnes(string s) {
        int one = 0, zero = 0, maxOne = 0, maxZero = 0;
        for (char c : s) {
            if (c == '0') {
                one = 0;
                ++zero;
                maxZero = max(maxZero, zero);
            } else {
                zero = 0;
                ++one;
                maxOne = max(maxOne, one);
            }
        }
        return maxOne > maxZero;
    }
};