algoadvance

Leetcode 1869. Longer Contiguous Segments of Ones than Zeros

Problem Statement

  1. Longer Contiguous Segments of Ones than Zeros

You are given a binary string s that contains only characters '0' and '1'. A binary string is a string that consists only of characters '0' and '1'.

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

Clarifying Questions:

  1. Can the string be empty?
    • No, as we are given a binary string, it will contain at least one character.
  2. Are there constraints on the string’s length?
    • The constraint as per LeetCode is typically manageable within the context of an interview, typically up to 10^5 characters.
  3. Should the function be case-sensitive?
    • No, as the problem specifies the string will only contain 0s and 1s.
  4. What should the output be if the length of the longest segment of 1s is equal to the longest segment of 0s?
    • The output should be false as per the problem’s requirement for a “strictly longer” segment of 1s.

Strategy

  1. Traverse the binary string and keep track of the longest contiguous segment of 1s and the longest contiguous segment of 0s.
  2. Iterate through the string while maintaining counters for consecutive 1s and 0s.
  3. Compare the longest segment lengths and return the appropriate boolean result.

Code

public class Solution {
    public boolean checkZeroOnes(String s) {
        int maxOnes = 0, maxZeros = 0;
        int currentOnes = 0, currentZeros = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '1') {
                currentOnes++;
                currentZeros = 0;
                maxOnes = Math.max(maxOnes, currentOnes);
            } else {
                currentZeros++;
                currentOnes = 0;
                maxZeros = Math.max(maxZeros, currentZeros);
            }
        }
        
        return maxOnes > maxZeros;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.checkZeroOnes("1101")); // true
        System.out.println(sol.checkZeroOnes("111000")); // false
        System.out.println(sol.checkZeroOnes("110100010")); // false
    }
}

Time Complexity

The time complexity of the solution is O(n) where n is the length of the input string s. This is because we are performing a single pass through the string.

Explanation of Code:

  1. We initialize maxOnes and maxZeros to keep track of the maximum segments of 1s and 0s respectively.
  2. currentOnes and currentZeros are initialized to count the length of the current segments of 1s and 0s while iterating.
  3. We iterate through each character in the string:
    • If the character is '1', we increment currentOnes, reset currentZeros to 0, and update maxOnes if currentOnes is greater.
    • If the character is '0', we increment currentZeros, reset currentOnes to 0, and update maxZeros if currentZeros is greater.
  4. After the loop, we compare maxOnes with maxZeros and return true if maxOnes is greater, otherwise false.

This approach ensures that we efficiently determine the longest contiguous segments of 1s and 0s and return the correct result based on the problem’s requirements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI