algoadvance

You are given a binary string s (a string consisting only of ‘0’s and ‘1’s). You need to check if the binary string has at most one contiguous segment of ‘1’s. Return True if the string contains at most one segment of ‘1’s, otherwise return False.

Example:

• Input: s = "1001"
  • Output: False
• Input: s = "110"
  • Output: True

Clarifying Questions

• Should we handle empty strings?
  • As per problem constraints, the input string s is non-empty.
• Are leading or trailing zeroes significant in the count of segments of ones?
  • Yes, we only care about contiguous segments of ‘1’s within the string.

Strategy

To solve this problem, we’ll:

1. Traverse the string looking for transitions between ‘0’ to ‘1’ and ‘1’ to ‘0’.
2. Count the number of segments of ‘1’s.
3. If the count of segments of ‘1’s is greater than 1, return False; otherwise, return True.

Code

def checkOnesSegment(s: str) -> bool:
    count_segments = 0
    in_segment = False
    
    for char in s:
        if char == '1':
            if not in_segment:
                count_segments += 1
                if count_segments > 1:
                    return False
                in_segment = True
        else:
            in_segment = False
                
    return True

# Example usage
print(checkOnesSegment("1001"))  # Output: False
print(checkOnesSegment("110"))   # Output: True

Time Complexity

• The time complexity of this solution is O(n), where n is the length of the string s. This is because we traverse the string once.
• The space complexity is O(1) since we only use a few additional variables.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?