We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Substrings With Fixed Ratio

Number: 2629

Difficulty: Medium

Paid? Yes

Companies: Intuit

Problem Description

Given a binary string s and two coprime integers num1 and num2, count the number of non-empty substrings (contiguous sequences) of s such that the ratio between the number of 0's and the number of 1's is exactly num1 : num2. Since num1 and num2 are coprime, any substring with the correct ratio must consist of counts that are multiples of num1 and num2 respectively.

Key Insights

  • Transform the ratio condition into an equation: For a substring with count0 zeros and count1 ones, we require count0 * num2 == count1 * num1. Since num1 and num2 are coprime, this implies count0 = k * num1 and count1 = k * num2 for some k.
  • Instead of counting zeros and ones directly over all substrings (which would be too slow), use a prefix sum technique.
  • Modify the prefix sum so that when reading a character, if the value is a '0', add num2 and if it is a '1', subtract num1. The logic is that a valid substring (i.e. one satisfying the ratio) will have a net change of zero.
  • Count the number of pairs of indices with equal prefix sum differences. The frequency of a given prefix sum delta allows you to calculate the number of valid substrings ending anywhere.
  • Use a hash table (dictionary) to record how many times a particular prefix sum appears.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, because we make one pass through s and perform O(1) operations per character. Space Complexity: O(n) in the worst case, due to storage of prefix sum counts in a hash table.

Solution

The solution involves iterating through the binary string while calculating a modified prefix sum. When processing each character:

  • If the character is '0', add num2 to the prefix sum.
  • If the character is '1', subtract num1 from the prefix sum.

A substring from index i+1 to j will have a net sum of 0 if the prefix sum at j equals the prefix sum at i. We count the number of occurrences of each prefix sum in a hash table. After processing the string, for every prefix sum value that appears f times, the number of valid substrings contributed from that value can be computed as combinations of 2 from f (i.e., f * (f - 1) / 2).

It is important to initialize the prefix sum hash table with the value 0 having a count of 1, representing the empty prefix, so that substrings starting from index 0 are correctly counted.

Code Solutions

# Python solution for Number of Substrings With Fixed Ratio

def fixed_ratio_substrings(s, num1, num2):
    # Dictionary to store frequency count of prefix sums
    prefix_counts = {}
    # Initialize with prefix sum 0 to handle substrings starting at index 0
    prefix_counts[0] = 1
    
    prefix_sum = 0  # modified prefix sum
    result = 0
    
    # Iterate over each character in the string
    for char in s:
        if char == '0':
            # Add num2 for character '0'
            prefix_sum += num2
        else:  # char == '1'
            # Subtract num1 for character '1'
            prefix_sum -= num1
        
        # If prefix_sum already seen, add its frequency to result
        # because it forms valid substrings with previous indices
        if prefix_sum in prefix_counts:
            result += prefix_counts[prefix_sum]
            prefix_counts[prefix_sum] += 1
        else:
            prefix_counts[prefix_sum] = 1
    
    return result

# Example usage:
print(fixed_ratio_substrings("0110011", 1, 2))  # Expected output: 4
← Back to All Questions