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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if Binary String Has at Most One Segment of Ones

Number: 1910

Difficulty: Easy

Paid? No

Companies: Cisco

Problem Description

Given a binary string s (with no leading zeros), determine if the string contains at most one contiguous segment of ones. For example, "110" has one contiguous segment of ones and should return true, while "1001" has two separate segments of ones and should return false.

Key Insights

  • The goal is to determine if there is more than one continuous block of '1's in the string.
  • A simple iteration through the string while tracking transitions from '1' to '0' can help detect the end of a segment.
  • Once the first segment of ones ends, any later occurrence of '1' implies there is a second segment.
  • The solution leverages a state flag to recognize when a segment of ones is active and when it has ended.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we perform a single pass. Space Complexity: O(1), using only constant extra space.

Solution

We iterate through the string while maintaining a boolean flag to indicate if we are currently in a segment of ones. Once we exit a segment (detecting a transition from '1' to '0'), if we later encounter another '1', we immediately return false. This approach ensures we only allow one contiguous segment of ones throughout the string.

Code Solutions

# Python solution for checking if the binary string has at most one segment of ones.

def checkOnesSegment(s):
    # Flag to indicate whether we have ended a segment of ones
    segmentEnded = False
    # Iterate through each character in the string
    for char in s:
        if char == '1':
            # If we see a 1 after a segment has ended, it means there's a new segment.
            if segmentEnded:
                return False
        else:  # char == '0'
            # Once we encounter '0', we mark that any following '1' is a new segment.
            segmentEnded = True
    return True

# Example usage:
print(checkOnesSegment("1001"))  # Output: False
print(checkOnesSegment("110"))   # Output: True
← Back to All Questions