Jobs

Interviews

Discussions

Check if Binary String Has at Most One Segment of Ones

Easy

Cisco

2 views

Topics:

Strings

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

Example 1:

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

Example 2:

Input: s = "110"
Output: true

Constraints:

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

Try coding it in LeetCode

Check if Binary String Has at Most One Segment of Ones

Easy

Cisco

2 views

Topics:

Strings

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

Example 1:

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

Example 2:

Input: s = "110"
Output: true

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the binary string?
Can the input string be empty or null?
If the string contains no '1's at all, should I return true or false?
Is the input guaranteed to only contain '0' and '1' characters?
Could you clarify what is considered a 'contiguous segment'? For example, does '110011' have two segments of ones ('11' and '11')?

Brute Force Solution

Approach

The brute force method for this problem is straightforward: examine the entire string of zeroes and ones character by character. The goal is to identify if there is a single, unbroken sequence of ones, possibly surrounded by zeroes.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the string.
Move through the string one character at a time.
As you go, look for the very first time you see a zero.
If you don't find any zeros, the string is all ones which fulfills the at most one segment of ones requirement, and you're done.
If you do find a zero, keep going, looking for the next one.
If, after finding a zero, you find a one again, this means there are two segments of ones, so the string does not fulfill the requirement.
If you reach the end of the string after the initial zero without seeing another one, the string fulfills the one segment of ones requirement.

Code Implementation

def check_if_binary_string_has_at_most_one_segment_of_ones(binary_string):
    number_of_characters = len(binary_string)
    index = 0

    # Iterate to find the end of the first segment of ones.
    while index < number_of_characters and binary_string[index] == '1':
        index += 1

    # If the whole string is ones, return True.
    if index == number_of_characters:
        return True

    # Skip all the zeros.

    while index < number_of_characters and binary_string[index] == '0':
        index += 1

    # Check if there are any more ones after the zeros.
    # If we find any ones after zeros, it's not a single segment.
    if index < number_of_characters:
        return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n at most once. In the worst-case scenario, it traverses the entire string to either find the first zero or to confirm that no zeros exist. After encountering a zero, it continues to scan the remainder of the string to check if another one appears. Therefore, the number of operations grows linearly with the length of the string, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm iterates through the input string but does not use any auxiliary data structures like arrays, hashmaps, or trees to store intermediate results. It only uses a fixed number of variables to track the state (whether a zero has been seen and whether a one has been seen after a zero). Therefore, the space used remains constant regardless of the input string's length, N.

Optimal Solution

Approach

The problem asks us to check if a string of ones and zeros has at most one continuous block of ones. The efficient way is to scan the string and look for a specific pattern: a zero followed by a one.

Here's how the algorithm would work step-by-step:

Go through the string character by character, from beginning to end.
Look for a spot where a zero is immediately followed by a one.
If you find a zero followed by a one, it means there's a break in the sequence of ones, followed by another sequence of ones. In other words, there is more than one segment of ones.
If you find a zero followed by a one, you can immediately say the string does NOT have at most one segment of ones and stop looking.
If you reach the end of the string without finding a zero followed by a one, it means either there is only one segment of ones, or there are no ones at all. In both cases, the string HAS at most one segment of ones.

Code Implementation

def check_if_binary_string_has_at_most_one_segment_of_ones(binary_string):
    found_zero = False

    for i in range(len(binary_string)): 
        if binary_string[i] == '0':
            # Record the first occurence of zero.
            found_zero = True

        if found_zero:
            # After the first zero, look for ones.
            if binary_string[i] == '1':
                # If we find a one, it's not one segment.
                return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string of length n character by character, examining each adjacent pair to check for the '01' pattern. In the worst-case scenario, the entire string is traversed. Therefore, the time complexity is directly proportional to the length of the string, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input string character by character without using any auxiliary data structures that scale with the input size N (the length of the binary string). It only uses a constant amount of extra space, specifically for loop counters or index variables. These variables consume a fixed amount of memory regardless of the string's length. Therefore, the space complexity is O(1), indicating constant space usage.

Edge Cases

Case	How to Handle
Empty string	Return true, as an empty string has zero segments of ones, which is at most one.
String with only '0's	Return true, as there are no segments of ones, which is at most one.
String with only '1's	Return true, as the entire string is a single segment of ones.
String starts and ends with '1's, with '0's in between	Return true, as it's a single contiguous segment of ones.
String contains multiple segments of '1's separated by '0's	Return false, as it violates the 'at most one segment' condition.
String with a single '1' at the beginning	Return true if the rest are zeros.
String with a single '1' at the end	Return true if the front are zeros.
String with '0's followed by '1's followed by '0's	Return true, as there is only one segment of ones.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the binary string?
Can the input string be empty or null?
If the string contains no '1's at all, should I return true or false?
Is the input guaranteed to only contain '0' and '1' characters?
Could you clarify what is considered a 'contiguous segment'? For example, does '110011' have two segments of ones ('11' and '11')?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very beginning of the string.
Move through the string one character at a time.
As you go, look for the very first time you see a zero.
If you don't find any zeros, the string is all ones which fulfills the at most one segment of ones requirement, and you're done.
If you do find a zero, keep going, looking for the next one.
If, after finding a zero, you find a one again, this means there are two segments of ones, so the string does not fulfill the requirement.
If you reach the end of the string after the initial zero without seeing another one, the string fulfills the one segment of ones requirement.

Code Implementation

def check_if_binary_string_has_at_most_one_segment_of_ones(binary_string):
    number_of_characters = len(binary_string)
    index = 0

    # Iterate to find the end of the first segment of ones.
    while index < number_of_characters and binary_string[index] == '1':
        index += 1

    # If the whole string is ones, return True.
    if index == number_of_characters:
        return True

    # Skip all the zeros.

    while index < number_of_characters and binary_string[index] == '0':
        index += 1

    # Check if there are any more ones after the zeros.
    # If we find any ones after zeros, it's not a single segment.
    if index < number_of_characters:
        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The problem asks us to check if a string of ones and zeros has at most one continuous block of ones. The efficient way is to scan the string and look for a specific pattern: a zero followed by a one.

Here's how the algorithm would work step-by-step:

Go through the string character by character, from beginning to end.
Look for a spot where a zero is immediately followed by a one.
If you find a zero followed by a one, it means there's a break in the sequence of ones, followed by another sequence of ones. In other words, there is more than one segment of ones.
If you find a zero followed by a one, you can immediately say the string does NOT have at most one segment of ones and stop looking.
If you reach the end of the string without finding a zero followed by a one, it means either there is only one segment of ones, or there are no ones at all. In both cases, the string HAS at most one segment of ones.

Code Implementation

def check_if_binary_string_has_at_most_one_segment_of_ones(binary_string):
    found_zero = False

    for i in range(len(binary_string)): 
        if binary_string[i] == '0':
            # Record the first occurence of zero.
            found_zero = True

        if found_zero:
            # After the first zero, look for ones.
            if binary_string[i] == '1':
                # If we find a one, it's not one segment.
                return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string	Return true, as an empty string has zero segments of ones, which is at most one.
String with only '0's	Return true, as there are no segments of ones, which is at most one.
String with only '1's	Return true, as the entire string is a single segment of ones.
String starts and ends with '1's, with '0's in between	Return true, as it's a single contiguous segment of ones.
String contains multiple segments of '1's separated by '0's	Return false, as it violates the 'at most one segment' condition.
String with a single '1' at the beginning	Return true if the rest are zeros.
String with a single '1' at the end	Return true if the front are zeros.
String with '0's followed by '1's followed by '0's	Return true, as there is only one segment of ones.