DEV Community

Cover image for 💥 Beginner-Friendly Guide 'Check if Binary String Has at Most One Segment of Ones' - Problem 1784 (C++, Python, JavaScript)
Om Shree
Om Shree

Posted on

💥 Beginner-Friendly Guide 'Check if Binary String Has at Most One Segment of Ones' - Problem 1784 (C++, Python, JavaScript)

#programming #cpp #javascript #python

Binary strings often appear simple, but they are the foundation of how data is stored and processed in every computer. Mastering how to traverse these strings and identify patterns is a fundamental skill for any aspiring software engineer.

Problem Summary

You're given:

  • A binary string $s$ consisting only of characters '0' and '1'.
  • The guarantee that $s$ does not have leading zeros, meaning it always starts with '1'.

Your goal:

  • Return true if the string contains at most one contiguous segment of ones.
  • Return false if there are multiple separated segments of ones.

Intuition

The problem states that the string always starts with a '1'. If there is only one segment of ones, all the '1's must be clustered at the beginning or stay together without being interrupted by a '0'.

If we ever see a '0' followed immediately by a '1' (the pattern "01"), it means a new segment of ones has started after a gap. Since we are only allowed one segment, the presence of the substring "01" is the "smoking gun" that tells us the condition has been violated.

Walkthrough: Understanding the Examples

Example 1: s = "1001"

  1. We start at the beginning. We see "1".
  2. We move to the next characters and see "00".
  3. Suddenly, we see a "1" following a "0". This forms the pattern "01".
  4. Because a new segment of ones started after a zero, we return false.

Example 2: s = "110"

  1. We start with "11".
  2. We see a "0" at the end.
  3. We never encounter a "1" appearing after that "0".
  4. Since there is no "01" pattern, there is only one segment. We return true.

C++ Solution 

class Solution {
public:
    bool checkOnesSegment(string s) {
        // If "01" is not found, s.find returns string::npos
        return s.find("01") == string::npos;
    }
};
Enter fullscreen mode Exit fullscreen mode

Python Solution 

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        # The 'in' operator returns True if the substring exists
        # We want True if it does NOT exist
        return "01" not in s
Enter fullscreen mode Exit fullscreen mode

JavaScript Solution 

/**
 * @param {string} s
 * @return {boolean}
 */
var checkOnesSegment = function(s) {
    // includes() returns true if the pattern is found
    // We negate it because we want true if the segment is contiguous
    return !s.includes("01");
};
Enter fullscreen mode Exit fullscreen mode

Key Takeaways

  • Pattern Recognition: Sometimes a complex-sounding problem (counting contiguous segments) can be simplified into searching for a specific sub-pattern.
  • String Searching: Understanding built-in string methods like find, includes, or in can lead to highly efficient and readable $O(n)$ solutions.
  • Constraints Matter: The fact that there are no leading zeros ($s[0]$ is always '1') is the key piece of information that allows the "01" check to work perfectly.

Final Thoughts

This problem is a fantastic example of how software engineers optimize code. While you could write a complex loop with multiple counters and state variables, identifying the "01" pattern allows for a "one-liner" solution. This type of logic is frequently used in data validation and stream processing, where you need to ensure data packets follow a specific format without overhead.

Top comments (0)