LeetCode 696: Count Binary Substrings Solution

Master LeetCode problem 696 (Count Binary Substrings), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

696. Count Binary Substrings

Easy

Two Pointers String

Problem Explanation

Explanation

To solve this problem, we can iterate through the binary string s and count the number of consecutive 0's and 1's. For each index i, we can find the number of consecutive 0's and 1's starting from that index. The number of valid substrings formed at index i will be the minimum of the counts of consecutive 0's and 1's starting from that index. We can then sum up the counts for all indices to get the total number of valid substrings.

Algorithm:

Initialize variables prevCount, currCount, totalCount to 0.
Iterate through the binary string s:
- If the current character is different from the previous character, update prevCount to currCount and reset currCount to 1.
- If the current character is the same as the previous character, increment currCount.
- If prevCount >= currCount, increment totalCount.
Return totalCount as the result.

Time Complexity: O(n) where n is the length of the input string s. Space Complexity: O(1)

Solution Code

class Solution {
    public int countBinarySubstrings(String s) {
        int prevCount = 0, currCount = 1, totalCount = 0;
        
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                prevCount = currCount;
                currCount = 1;
            } else {
                currCount++;
            }
            if (prevCount >= currCount) {
                totalCount++;
            }
        }
        
        return totalCount;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 696 (Count Binary Substrings)?

This page provides optimized solutions for LeetCode problem 696 (Count Binary Substrings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 696 (Count Binary Substrings)?

The time complexity for LeetCode 696 (Count Binary Substrings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 696 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 696 in Java, C++, or Python.

Back to LeetCode Solutions