Leetcode 1784: Check if Binary String Has at Most One Segment of Ones

Input: You are given a binary string s that does not have leading zeros. The string is made up of '0's and '1's.

Example: s = '101'

Constraints:

• 1 <= s.length <= 100

• s[i] is either '0' or '1'

• s[0] is '1'

Output: Return true if the string contains at most one contiguous block of '1's. Otherwise, return false.

Example: Input: s = '111', Output: true

Constraints:

Goal: The goal is to determine if there is only one contiguous block of '1's in the string.

Steps:

• 1. Search for the substring '01' in the string.

• 2. If the substring '01' is found, return false since there are multiple blocks of '1's.

• 3. If no such substring is found, return true as the '1's form one contiguous block.

Goal: The binary string s must not have leading zeros and the length must be between 1 and 100.

Steps:

• 1 <= s.length <= 100

• s[i] is either '0' or '1'

• s[0] is '1'

Assumptions:

• The binary string s starts with a '1'.

• The string contains only '0's and '1's.

• Input: Input: s = '101'

• Explanation: The ones in the string are not contiguous, as there is a '0' between them. Hence, the result is false.

• Input: Input: s = '111'

• Explanation: The ones form a single contiguous block, so the result is true.

Approach: We can simply check for the presence of the substring '01' in the string. If it exists, it indicates that the '1's are not contiguous.

Observations:

• The problem can be solved by checking for the '01' substring.

• The solution relies on recognizing that once the first block of '1's ends, if another '1' starts after a '0', the blocks are separate.

Steps:

• 1. Iterate through the string to find if there is any occurrence of the substring '01'.

• 2. If the substring is found, return false.

• 3. If no '01' substring is found, return true.

Empty Inputs:

• Input string s will not be empty as per the constraints.

Large Inputs:

• Ensure that the solution handles strings of maximum length (100 characters).

Special Values:

• If the string contains only one '1', it should return true.

Constraints:

• The string must contain at least one '1' due to the constraint that s[0] is '1'.

bool checkOnesSegment(string s) {

    // without leading zeros mean starting with 1s
    // if another set of one comes, there be definitely a 01
    // thats all
    return string::npos == s.find("01");
}

1 : Function Definition

bool checkOnesSegment(string s) {

Define the function `checkOnesSegment`, which takes a string `s` as input and returns a boolean indicating whether the string contains a single contiguous segment of 1's.

2 : Return Statement

    return string::npos == s.find("01");

The function checks if the string 's' contains the substring '01' (indicating a break in the segment of 1's). If '01' is found, the function returns `false`. Otherwise, it returns `true`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we perform a single scan of the string to find the substring.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) since no additional space is required apart from the input string.

Leetcode 1784: Check if Binary String Has at Most One Segment of Ones

Explore →