algoadvance

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

Problem Statement

You are given a binary string s which contains only characters '0' and '1'. A segment is a contiguous substring of the binary string. The problem asks to determine if the binary string has at most one segment of ones, meaning that all the 1s in the string are grouped together in one contiguous segment, without being separated by any 0s. If the string meets this condition, return true, otherwise return false.

Clarifying Questions

  1. Input Constraints:

    • What is the length range of the input string?

      The length of the binary string can range from 1 to 1000.

  2. Output:

    • Should we return a boolean value indicating if the string meets the condition?

      Yes, return true if the string meets the condition, otherwise return false.

  3. Edge Cases:

    • How should the function handle strings that consist entirely of 0s or 1s?

      If the string consists entirely of 0s or 1s, it should return true.

  4. Assumptions:

    • Can the string contain characters other than ‘0’ and ‘1’?

      No, the string will only contain ‘0’ and ‘1’.

Strategy

To solve this problem, we need to ensure there is at most one contiguous segment of 1s in the string s.

  1. Identify the first occurrence of ‘1’: Traverse the string until finding the first ‘1’.
  2. Check for a contiguous segment: After finding the first ‘1’, ensure no ‘0’ is found followed by another ‘1’.
  3. Validation: If we encounter ‘0’ after the first segment of ‘1’s, the string should not have any further ‘1’s. If it does, return false.

Code

Here is an implementation in C++:

#include <iostream>
#include <string>

bool checkOnesSegment(const std::string& s) {
    bool foundOneSegment = false;
    
    for (size_t i = 0; i < s.size(); ++i) {
        if (s[i] == '1') {
            if (foundOneSegment && s[i - 1] == '0') {
                // A new '1' segment is found after '0', hence return false
                return false;
            }
            foundOneSegment = true;  // Mark that we have found a '1' segment
        }
    }
    return true;  // No disjoint segments of '1' found
}

int main() {
    std::string test1 = "10001";
    std::string test2 = "1001";
    std::string test3 = "110";
    std::string test4 = "1111";
    
    std::cout << checkOnesSegment(test1) << std::endl;  // Output: false
    std::cout << checkOnesSegment(test2) << std::endl;  // Output: false
    std::cout << checkOnesSegment(test3) << std::endl;  // Output: true
    std::cout << checkOnesSegment(test4) << std::endl;  // Output: true
    
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string. This is because we make a single pass through the string to check for contiguous segments of ‘1’s.

The space complexity is O(1) as we use a constant amount of extra space regardless of the input size.

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