algoadvance

Leetcode 696. Count Binary Substrings

Problem Statement

Given a binary string s, return the number of non-empty substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example

Input: s = "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: 
"0011", "01", "1100", "10", "0011", and "01".

Input: s = "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01".

Clarifying Questions

1. Can the input string contain characters other than ‘0’ and ‘1’?
   • No, the problem guarantees that the input is a binary string consisting only of ‘0’s and ‘1’s.
2. What is the maximum length of the input string?
   • The problem statement doesn’t specify, but typically for such problems, it could be in the range of 10^5 or 10^6.
3. Should we consider overlapping substrings as distinct?
   • Yes, overlapping substrings should be counted separately if they occur multiple times.

Strategy

1. Group Counting:
   • Traverse the string and count consecutive segments of ‘0’s and ‘1’s.
   • Store these counts in a list.
2. Compute Substrings:
   • For each pair of consecutive groups in the list, the number of valid substrings between them is the minimum of the sizes of these two groups.

By following this approach, we can ensure linear time complexity.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int countBinarySubstrings(String s) {
        List<Integer> groupCounts = new ArrayList<>();
        int count = 1;
        
        // First, count consecutive '0's and '1's
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                groupCounts.add(count);
                count = 1;
            }
        }
        
        groupCounts.add(count);  // Add the last counted group
        
        // Secondly, count the valid substrings between each pair of consecutive groups
        int result = 0;
        for (int i = 1; i < groupCounts.size(); i++) {
            result += Math.min(groupCounts.get(i - 1), groupCounts.get(i));
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countBinarySubstrings("00110011"));  // Output: 6
        System.out.println(sol.countBinarySubstrings("10101"));     // Output: 4
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the string. This is because the algorithm involves two linear passes: one for counting the groups and one for calculating the number of valid substrings.

• Space Complexity: O(n) in the worst case, as we might store all group counts in the list. However, this could be optimized if needed by using a constant number of variables instead of a list.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?