Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The input is guaranteed to begin with one, so its first ones segment has already started. A second segment exists exactly when a zero is followed by a one somewhere later. Without the no-leading-zeros guarantee, this shortcut would not correctly count segments.

Approach

Search the string for 01 and return whether it is absent. If found, the earlier starting one, intervening zero, and new one establish separate segments. If absent, once the string leaves its initial run of ones, it can contain only zeros afterward. An all-ones string therefore succeeds.

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

Complexity analysis

Let n = s.length. Time: O(n) for the substring search. Auxiliary space: O(1).