Leetcode 696 Solution

This article provides solution to leetcode question 696 (count-binary-substrings)
Categories:
Tags:
Access this page by simply typing in "lcs 696" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/count-binary-substrings

Solution

class Solution {
public:
    int countBinarySubstrings(string s) {
        vector<int> v(s.size(), 1);

        int res = 0;

        for (int i = 1; i < s.size(); i++)
        {
            if (s[i] != s[i - 1])
                res += 1;
            else
            {
                int j = i - v[i - 1] - 1;
                if (j >= 0 && v[j] >= v[i - 1] + 1)
                    res += 1;

                v[i] += v[i - 1];
            }
        }

        return res;
    }
};