Check if Binary String Has at Most One Segment of Ones

Easy
636.

Check if Binary String Has at Most One Segment of Ones

Check if Binary String Has at Most One Segment of Ones is an easy coding problem on strings, asked in TCS, Infosys and Accenture interviews.

A segment of ones is a maximal run of consecutive '1' characters.

Given a binary string s whose first character is '1', return true if it contains at most one such segment.

Example 1

Input
s = "1001"
Output
false
Explanation
Two segments: the leading 1 and the trailing 1.

Example 2

Input
s = "110"
Output
true
Explanation
One segment.

Example 3

Input
s = "1"
Output
true

Constraints

  • 1 <= s.length <= 100
  • s[i] is '0' or '1'
  • s[0] is '1'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {boolean}
 */
var checkOnesSegment = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Check if Binary String Has at Most One Segment of Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check if Binary String Has at Most One Segment of Ones is an easy coding problem on strings, asked in TCS, Infosys and Accenture interviews.

  • Difficulty: Easy
  • Topics: Strings
  • Asked at: TCS, Infosys, Accenture
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A segment of ones is a maximal run of consecutive '1' characters.

Given a binary string s whose first character is '1', return true if it contains at most one such segment.

Example 1

Input: s = "1001"
Output: false
Explanation: Two segments: the leading 1 and the trailing 1.

Example 2

Input: s = "110"
Output: true
Explanation: One segment.

Example 3

Input: s = "1"
Output: true

Constraints

  • 1 <= s.length <= 100
  • s[i] is '0' or '1'
  • s[0] is '1'.

Hints for Check if Binary String Has at Most One Segment of Ones

  1. Hint 1

    A new segment starts exactly where a '1' follows a '0' (or begins the string).

  2. Hint 2

    Count those starts and compare with 1.

  3. Hint 3

    Because the string starts with '1', an equivalent check is simply: does "01" appear anywhere?

How to solve Check if Binary String Has at Most One Segment of Ones

Segments are counted by their starting positions: a '1' whose predecessor is a '0' (or which is the first character) opens a new run. At most one such start means at most one segment.

Approach

  1. Sweep the string counting positions where s[i] == '1' and either i == 0 or s[i-1] == '0'.
  2. Return whether that count is at most 1.

Why it works

Every maximal run of ones has exactly one starting position under that test, and every position passing the test opens a run — so the count is exactly the number of segments.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Counting '1' characters rather than run starts answers a different question entirely.
  • The guarantee that s[0] == '1' is what makes the shortcut 'does the string contain 01' valid — without it, "0110" would fool it.

Reference solution

Python

def checkOnesSegment(s: str) -> bool:
    segments = 0
    for i, c in enumerate(s):
        if c == "1" and (i == 0 or s[i - 1] == "0"):
            segments += 1
    return segments <= 1

Java

public static boolean checkOnesSegment(String s) {
    int segments = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '1' && (i == 0 || s.charAt(i - 1) == '0')) segments++;
    }
    return segments <= 1;
}

C++

bool checkOnesSegment(string s) {
    int segments = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (s[i] == '1' && (i == 0 || s[i - 1] == '0')) segments++;
    }
    return segments <= 1;
}

JavaScript

var checkOnesSegment = function(s) {
    var segments = 0;
    for (var i = 0; i < s.length; i++) {
        if (s.charAt(i) === "1" && (i === 0 || s.charAt(i - 1) === "0")) segments++;
    }
    return segments <= 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings