I am going through this programming task : Count of sub-strings with equal consecutive 0’s and 1’s,

Given binary string str of 0’s and 1’s only. The task is to count the total numbers of substrings of string str such that each substring has an equal number of consecutive 0’s and 1’s in it.

Example :

Input: str = “010011” 
Output: 4 

Explanation:

The substrings with consecutive 0’s and 1’s are “01”, “10”, “0011”, “01”. Hence, the count is 4. 

Note:

The two “01” are at different positions: [0, 1] and [3, 4]. 
“010011” has the same number of 0’s and 1’s but they are not consecutive.

Example :

Input: str = “0001110010” 
Output: 7

Explanation:

The substrings with consecutive 0’s and 1’s are “000111”, “0011”, “01”, “1100”, “10”, “01”, “10”.

This is the Java program for it:

class GFG{
 
    // Function to find the count
    // of substrings with equal no.
    // of consecutive 0's and 1's
    static int countSubstring(String S, int n)
    {
        // To store the total count
        // of substrings
        int ans = 0;
     
        int i = 0;
     
        // Traversing the string
        while (i < n) {
     
            // Count of consecutive
            // 0's & 1's
            int cnt0 = 0, cnt1 = 0;
     
            // Counting subarrays of
            // type "01"
            if (S.charAt(i) == '0') {
     
                // Count the consecutive
                // 0's
                while (i < n && S.charAt(i) == '0') {
                    cnt0  ;
                    i  ;
                }
     
                // If consecutive 0's
                // ends then check for
                // consecutive 1's
                int j = i;
     
                // Counting consecutive 1's
                while (j < n && S.charAt(j) == '1') {
                    cnt1  ;
                    j  ;
                }
            }
     
            // Counting subarrays of
            // type "10"
            else {
     
                // Count consecutive 1's
                while (i < n && S.charAt(i) == '1') {
                    cnt1  ;
                    i  ;
                }
     
                // If consecutive 1's
                // ends then check for
                // consecutive 0's
                int j = i;
     
                // Count consecutive 0's
                while (j < n && S.charAt(j) == '0') {
                    cnt0  ;
                    j  ;
                }
            }
     
            // Update the total count
            // of substrings with
            // minimum of (cnt0, cnt1)
            ans  = Math.min(cnt0, cnt1);
        }
     
        // Return answer
        return ans;
    }
     
    // Driver code
    static public void main(String args[])
    {
        String S = "0001110010";
        int n = S.length();
     
        // Function to print the
        // count of substrings
        System.out.println(countSubstring(S, n));
    }
}

The link says that : Time Complexity: O(N), where N = length of string.

But in this code, we have an outer look while (i < n) { and then inner loop while (i < n && S.charAt(i) == '0') and while (j < n && S.charAt(j) == '1'), so how this can be O(N) instead of O(N^2).

CodePudding user response：

We have two types of the inner loop. The first type is iterating over i. If the condition of this type is satisfied, thus the value of i in the outer loop will be increased as well. Hence, the sum of iterations will be in Theta(n).

The second type is iterating over j. The point is that if inside any of two conditions (if (S.charAt(i) == '0') or else) the j counter iterates k times (for example), it means that for the next iteration of the outer loop, the opposite condition will be true among if (S.charAt(i) == '0') and else. Hence, the inner loop over i iterates k times, and it increases the value of the outer loop k steps. Therefore, the sum of computations can be at most 2n in this case.

Consequently, the key point is in the dependency type of conditions and inner loops with the outer loop. Based on the explained dependency, this algorithm is in Theta(n) and O(n).