algoadvance

Leetcode 1784. Check if Binary String Has at Most One Segment of Ones

Problem Statement

Given a binary string s, we need to determine if it contains at most one contiguous segment of ones. For instance, the binary string “1001” has two contiguous segments of ones “1” and “1”, so it should return false. The binary string “110” contains one contiguous segment of ones “11”, so it should return true.

Clarifying Questions

  1. Input Format: Is the input always a non-empty string containing only ‘0’s and ‘1’s?
    • Yes.
  2. Output Format: Should the output be a boolean value?
    • Yes.

Strategy

  1. Identify Contiguous Segments: We need to scan through the string and identify the segments of ones.
  2. Count Segments: We can count the number of contiguous segments of ones.
  3. Return Result: If the count is more than one, return false; otherwise, return true.

Code

Here is the Java code to solve this problem:

public class Solution {
    public boolean checkOnesSegment(String s) {
        // Variable to count the segments of ones
        int segmentsCount = 0;
        
        // Traverse the string
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                // If we encounter a '1', check if it is the beginning of a new segment
                if (i == 0 || s.charAt(i - 1) != '1') {
                    segmentsCount++;
                    // If there is more than one segment, return false
                    if (segmentsCount > 1) {
                        return false;
                    }
                }
            }
        }
        
        // If we finish the loop and have no more than one segment of ones
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.checkOnesSegment("1001")); // Output: false
        System.out.println(solution.checkOnesSegment("110"));  // Output: true
        System.out.println(solution.checkOnesSegment("1110")); // Output: true
        System.out.println(solution.checkOnesSegment("01110"));// Output: true
    }
}

Time Complexity

By following this strategy and using the provided code, we can determine if the binary string contains at most one segment of contiguous ones efficiently.

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