Simple recursive solution


  • 0
    F

    Iterate through and find instance of "01" or "10". After you find that call a recursive sub function to find number of solutions from that point and add it to the result.

     class Solution {
        public int countBinarySubstrings(String s) {
            int res = 0;
            char[] sArray = s.toCharArray();
            for(int i = 1; i < sArray.length; i++) {
                char c1 = sArray[i-1];
                char c2 = sArray[i];
                if(c1 != c2) res += countValid(sArray, i-1, i);
            }
            return res;
        }
        
        public int countValid(char[] arr, int start, int end) {
            if(start < 0 || end >= arr.length) return 0;
            if(end-start == 1)
                return countValid(arr, start-1, end+1) + 1;
            if(arr[start+1] == arr[start] && arr[end-1] == arr[end])
                return countValid(arr, start-1, end+1) + 1;
            else
                return 0;
        }
    }
    

Log in to reply
 

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