Jave O(n) time O(1) space with explanation


  • 1
    S
    public int countBinarySubstrings(String s) {
            // only update res when current position is last char or current char not the same as next char
            // e.g. 00111, update res at 2nd 0 and 3rd 1. at 2nd 0, prvCount is 0, therefore res += 0
            // at 3rd 1, prvCount is 2, curCount is 3, res += 2
            // once res updated, assign curCount to prvCount, then reset curCount
            int prvCount = 0, curCount = 0, res = 0;
            for (int i = 0; i < s.length(); i++) {
                curCount ++;
                if (i == s.length()-1 || s.charAt(i) != s.charAt(i+1)) {
                    res += Math.min(prvCount, curCount);
                    prvCount = curCount;
                    curCount = 0;
                }
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.