696. Count Binary Substrings

 一刷 07/2022

Version #2 Iteration with optimized space

Time O(N)

Space O(1)

Runtime: 14 ms, faster than 61.35% of Java online submissions for Count Binary Substrings.

Memory Usage: 49.2 MB, less than 52.26% of Java online submissions for Count Binary Substrings.

class Solution {

    public int countBinarySubstrings(String s) {

        int result = 0;

        int prevCount = 0;

        int currCount = 0;

        for (int i = 0; i < s.length(); i++) {

            if (i == 0 || s.charAt(i) == s.charAt(i - 1)) {

                currCount++;

            } else {

                prevCount = currCount;

                currCount = 1;

            }

            // prev count

            if (prevCount >= currCount) {

                result++;

            }

        }

        return result;

    }

}

Version #1 Iteration with O(N) space

Time O(N)

Space O(N)

Runtime: 22 ms, faster than 14.97% of Java online submissions for Count Binary Substrings.

Memory Usage: 52.4 MB, less than 16.55% of Java online submissions for Count Binary Substrings.

class Solution {

    public int countBinarySubstrings(String s) {

        int result = 0;

        int[] count = new int[s.length()];

        count[0] = 1;

        for (int i = 1; i < s.length(); i++) {

            if (s.charAt(i) == s.charAt(i - 1)) {

                count[i] = count[i - 1] + 1;

            } else {

                count[i] = 1;

            }

            // prev count

            if (i - count[i] >= 0 && count[i - count[i]] >= count[i]) {

                result++;

            }

        }

        return result;

    }

}