Solution Explanation for 1784. Check if Binary String Has at Most One Segment of Ones

This problem asks to determine if a binary string (containing only '0's and '1's) has at most one contiguous segment of ones. The string is guaranteed to start with '1' and have no leading zeros.

Core Idea: The key observation is that if a binary string has more than one segment of consecutive ones, it must contain the substring "01". This is because a new segment of ones can only begin after a '0' follows a '1'. Conversely, if the substring "01" is absent, there can be at most one segment of consecutive ones.

Algorithm:

The most efficient approach is to simply check if the substring "01" exists within the input string s. If it does, the string has more than one segment of ones, and we return false. Otherwise, we return true.

Time and Space Complexity Analysis:

• Time Complexity: O(n), where n is the length of the string s. This is because the contains() or find() operation (depending on the language) has a linear time complexity in the worst case. The algorithm iterates through the string at most once.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input string's size. We're not creating any data structures whose size scales with the input.

Code Implementation in Multiple Languages:

The code implementations below reflect this straightforward approach. They all share the same core logic: checking for the presence of "01" in the input string.

Python3:

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

Java:

class Solution {
    public boolean checkOnesSegment(String s) {
        return !s.contains("01");
    }
}

C++:

class Solution {
public:
    bool checkOnesSegment(string s) {
        return s.find("01") == string::npos; // string::npos indicates substring not found
    }
};

Go:

func checkOnesSegment(s string) bool {
	return !strings.Contains(s, "01")
}

TypeScript:

function checkOnesSegment(s: string): boolean {
    return !s.includes('01');
}

Rust:

impl Solution {
    pub fn check_ones_segment(s: String) -> bool {
        !s.contains("01")
    }
}

All these implementations concisely express the core algorithm and achieve the optimal time and space complexity. The choice of language primarily affects syntax and minor details, but the underlying approach remains consistent.