We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if Binary String Has at Most One Segment of Ones

Difficulty: Easy

Problem Description

Given a binary string s without leading zeros, return true if s contains at most one contiguous segment of ones. Otherwise, return false.

Key Insights

  • The string consists of characters '0' and '1', with the first character guaranteed to be '1'.
  • We need to check if the ones in the string are contiguous, meaning there should not be any '0' between two segments of '1'.
  • A valid string will either have all '1's together or just a single segment of '1's surrounded by '0's.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(1) since we are only using a few variables for counting.

Solution

To determine if the binary string has at most one segment of ones, we can iterate through the string and keep track of the transitions between '0's and '1's. We will count how many times we encounter a transition from '0' to '1'. If we find more than one such transition, we can conclude that there are multiple segments of '1's, and we should return false. If there is at most one transition, we return true.

Code Solutions

def checkOnesSegment(s: str) -> bool:
    # Initialize a variable to count segments of '1's
    segments_of_ones = 0
    # Iterate through the string
    for i in range(len(s)):
        # If we encounter a '1' that is at the start or follows a '0', it's a new segment
        if s[i] == '1' and (i == 0 or s[i - 1] == '0'):
            segments_of_ones += 1
        # If there are more than one segments, return False
        if segments_of_ones > 1:
            return False
    # If we finish and have at most one segment, return True
    return True
← Back to All Questions