#1784

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Check if Binary String Has at Most One Segment of Ones

Check if a binary string contains at most one contiguous segment of ones.

Problem Statement

You are given a binary string s consisting of only '0's and '1's, where the first character is always '1'. Your task is to return true if there is at most one contiguous segment of '1's in the string. Otherwise, return false.

For example, if s = '1001', the output is false because there are two separate segments of '1's. For s = '110', the output is true because there is only one contiguous segment of '1's.

Examples

Example 1

Input: s = "1001"

Output: false

The ones do not form a contiguous segment.

Example 2

Input: s = "110"

Output: true

Example details omitted.

Constraints

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

Solution Approach

Identify Segments of '1's

The core idea is to scan the string for segments of '1's. A segment is a continuous sequence of '1's. If two separate segments are found, return false immediately.

Efficient Traversal

Iterate over the string just once. Track the number of segments of '1's encountered. If this count exceeds one, return false. The solution ensures linear time complexity.

Edge Case Handling

Consider edge cases where the string has minimal length or contains all '1's or all '0's. The logic should handle these without extra computation or errors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the string. This is because the string is scanned once to count the number of segments. The space complexity is O(1) as no extra data structures are used.

What Interviewers Usually Probe

Focus on counting segments of '1's efficiently.
Ensure the approach handles edge cases like all '1's or '0's.
Evaluate whether a more optimized solution can reduce redundant checks.

Common Pitfalls or Variants

Common pitfalls

Miscounting the segments due to improper string scanning.
Not handling edge cases like strings with no '1's or strings where all characters are '1'.
Overcomplicating the solution by introducing unnecessary data structures.

Follow-up variants

What if the string has leading or trailing zeros? The logic can be adapted to handle these cases effectively.
How would the solution change if we allowed the string to contain other characters? This introduces complexity in the segmentation logic.
Can we optimize further for strings with very large lengths? Explore constant space solutions.

FAQ

What is the solution approach for 'Check if Binary String Has at Most One Segment of Ones'?

The solution involves scanning the string to identify contiguous segments of '1's and counting them. If more than one segment is found, return false.

How does the string-driven approach help in solving this problem?

The string-driven approach allows you to focus on simple, efficient traversal of the binary string, making it easy to identify and count segments of '1's.

Are there any edge cases I should consider for this problem?

Yes, consider cases where the string consists of all '0's, all '1's, or just a single character. These cases may behave differently in your approach.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string, as we scan the string once to count the segments of '1's.

Can this problem be solved with a different approach?

While the string-driven approach is optimal, alternative methods might involve more complex data structures or a recursive approach. However, these might not be as efficient.

terminal

Solution

Solution 1: Brain Teaser

Since the string $s$ has no leading zeros, $s$ starts with `'1'`.

1

2

3

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        return '01' not in s

Continue Practicing

#1781 sum of beauty of all substrings #1790 check if one string swap can make strings equal #1773 count items matching a rule