LeetCode 1784. Check if Binary String Has at Most One Segment of Ones

Description

https://leetcode.com/problems/check-if-binary-string-has-at-most-one-segment-of-ones/

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'.

Explanation

Count ones as segments and check how many segments we got from the string

Python Solution

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        
        segments = []
        
        start = None
        end = None
        
        for i, c in enumerate(s):
            print (start)
            
            if c == '1':
                if start == None:
                    start = i
                    end = i
                else:
                    end = i
            else:
                if start != None and end != None:
                    segments.append([start, end])
                start = None
                end = None
        
        if start != None and end != None:
            segments.append([start, end])
        
        
        return len(segments) == 1
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.