Leetcode – Check if Binary String Has at Most One Segment of Ones Solution

Spread the love

The problem “Check if Binary String Has at Most One Segment of Ones” is a fascinating string manipulation challenge that tests your basic understanding of strings, loops, and conditions in Python. While the problem may initially appear trivial, it has subtle nuances that offer multiple approaches for solving it. This article aims to dissect the problem, present various solutions, and evaluate their performance in terms of time and space complexity.

Problem Statement

Given a binary string s (a string consisting only of ‘0’s and ‘1’s), we can split s into 3 non-empty strings s1, s2, s3 (s1 + s2 + s3 = s).

The string s is said to be good if and only if all three non-empty strings s1, s2, s3 do not contain any consecutive ‘1’s.

Return true if s is good, otherwise false.

Example:

Input: s = "1001"
Output: False

In this example, the string s has two segments of ‘1’s separated by ‘0’, making it impossible to split into three non-empty strings that do not contain consecutive ‘1’s.

Approach 1: Simple Looping

The most straightforward way to approach this problem is to iterate over the string and count the number of segments of ‘1’s.

Algorithm Steps:

  1. Initialize a variable segment_count to 0.
  2. Use a for loop to iterate through the string. If you find consecutive ‘1’s, continue iterating.
  3. When you find a ‘1’ after a ‘0’ or at the beginning of the string, increment segment_count.
  4. After the loop, check if segment_count <= 1.

Python Code:

def checkOnesSegment(s: str) -> bool:
    segment_count = 0
    for i in range(len(s)):
        if s[i] == '1':
            if i == 0 or s[i-1] == '0':
                segment_count += 1
    return segment_count <= 1

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string.
  • Space Complexity: O(1)

Approach 2: Using Built-in Functions

We can also use Python’s built-in string functions to make the code more concise.

Python Code:

def checkOnesSegment(s: str) -> bool:
    return s.split('0').count('1') <= 1

In this approach, we first use the split method to break the string into segments whenever a ‘0’ appears. Then we use the count method to count how many times ‘1’ appears as a whole segment.

Time and Space Complexity:

  • Time Complexity: O(n)
  • Space Complexity: O(n), as the split method creates a new list.

Approach 3: Regular Expressions

We can use Python’s re module to detect the number of segments containing consecutive ‘1’s.

Python Code:

import re

def checkOnesSegment(s: str) -> bool:
    return len(re.findall(r'1+', s)) <= 1

Here, we use the regular expression '1+', which will match one or more consecutive ‘1’s.

Time and Space Complexity:

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Approach 4: One-Liner Using str.split( )

If you are a fan of one-liners, you can solve this problem in a single line using the split method.

Python Code:

def checkOnesSegment(s: str) -> bool:
    return len([x for x in s.split('0') if x]) <= 1

This one-liner uses list comprehension to create a list of segments containing ‘1’s and then checks if its length is less than or equal to 1.

Time and Space Complexity:

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Conclusion

The “Check if Binary String Has at Most One Segment of Ones” problem serves as an excellent exercise to sharpen your skills in string manipulation, loop constructs, and built-in Python functionalities. It offers multiple avenues for solution, each highlighting different aspects of Python coding techniques.

Leave a Reply