Check If Binary String Has At Most One Segment Of Ones - Leetcode Solution

Problem Statement:

You are given a binary string s. You need to check if s has at most one segment of ones. A segment of ones is defined as a contiguous sequence of 1's in the string.

Solution:

The problem can be easily solved by using a simple algorithm. The approach is to traverse the input string s char by char, and to check if there are more than one segments of ones. If there are more than one segments of ones, then return False, else return True.

Algorithm:

1. Initialize a count variable to 0.
2. Traverse the input string s from the left to the right.
3. If the current character of s is '1', then increment the count variable.
4. If the count variable is greater than 1 and the current character of s is '1', then return False, as there is more than one segment of ones.
5. If the count variable becomes 0 and the current character of s is '0', then continue the loop, as there is no segment of ones yet.
6. If the count variable becomes 1 and the current character of s is '0', then continue the loop, as there is only one segment of ones so far.
7. If the loop completes without returning False, then return True, as there is at most one segment of ones in the string s.

Code Implementation:

Here is the python code implementation of the above algorithm:

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        count = 0
        for i in range(len(s)):
            if s[i] == '1':
                count += 1
                if count > 1 and s[i-1] == '1':
                    return False
            elif count == 1:
                continue
        return True

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the length of the input string s. As we are traversing the string s once, the time complexity is linear with respect to the length of the string.

Space Complexity:

The space complexity of the above algorithm is O(1), as we are using constant space to store the count variable.

1