Check if Binary String Has at Most One Segment of Ones

Difficulty: Easy | Acceptance: 49.10% | Paid: No Topics: String

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

• Examples
• Constraints
• Iteration with State Flag
• String Find Method
• Split and Count

Examples

Input: s = "1001"
Output: false
Explanation: The ones do not form a contiguous segment.

Input: s = "110"
Output: true
Explanation: The ones form a contiguous segment.

Constraints

1 <= s.length <= 100
s[i] is either '0' or '1'.
s[0] is '1'

Iteration with State Flag

Intuition Since the string has no leading zeros, it starts with a segment of ones. We iterate through the string. If we encounter a ‘0’, we know the first segment has ended. If we encounter a ‘1’ after that, it means a second segment has started, so we return false.

Steps

• Initialize a boolean flag seen_zero to false.
• Iterate through each character c in the string s.
• If c is ‘0’, set seen_zero to true.
• If c is ‘1’ and seen_zero is already true, return false.
• If the loop finishes without returning false, return true.

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        seen_zero = False
        for c in s:
            if c == '0':
                seen_zero = True
            elif seen_zero:
                return False
        return True

Complexity

• Time: O(n) where n is the length of the string.
• Space: O(1) auxiliary space.
• Notes: This is the most optimal approach as it scans the string only once.

String Find Method

Intuition A valid string with one segment of ones looks like 111...000.... It transitions from 1s to 0s at most once. This means the substring “01” (transition from 1 to 0) can appear at most once, and if it does, no “1” can appear after it.

Steps

• Find the index of the substring “01” in s.
• If “01” is not found, return true (the string is all 1s or 1s followed by 0s).
• If “01” is found, check if there is any “1” in the remaining substring starting from index + 2.
• If a “1” is found, return false; otherwise, return true.

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        idx = s.find("01")
        if idx == -1:
            return True
        return "1" not in s[idx + 2:]

Complexity

• Time: O(n) in the worst case, as string searching and slicing can take linear time.
• Space: O(1) auxiliary space, though slicing in some languages (like Python/JS) creates a new string copy.
• Notes: Concise but relies on built-in string methods which might have overhead.

Split and Count

Intuition If we split the string by ‘0’, the resulting array will contain strings consisting only of ‘1’s. If there is more than one non-empty string in this array, it means there were multiple segments of ones separated by zeros.

Steps

• Split the string s using the delimiter “0”.
• Iterate through the resulting parts and count how many parts are non-empty.
• If the count is greater than 1, return false.
• Otherwise, return true.

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        parts = s.split("0")
        count = 0
        for p in parts:
            if p:
                count += 1
        return count <= 1

Complexity

• Time: O(n) to split the string and iterate through parts.
• Space: O(n) to store the split array/parts.
• Notes: Less space efficient than the iteration approach due to the storage required for the split result.