Number of Substrings With Fixed Ratio - Practice Coding Problems

Number of Substrings With Fixed Ratio - Problem

You are given a binary string s, and two integers num1 and num2. num1 and num2 are coprime numbers.

A ratio substring is a substring of s where the ratio between the number of 0's and the number of 1's in the substring is exactly num1 : num2.

For example, if num1 = 2 and num2 = 3, then "01011" and "1110000111" are ratio substrings, while "11000" is not.

Return the number of non-empty ratio substrings of s.

Note that:

A substring is a contiguous sequence of characters within a string.
Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.

Input & Output

Example 1 — Basic Valid Substring

$ Input: s = "0110", num1 = 1, num2 = 2

› Output: 4

💡 Note: Substrings with 1:2 ratio (zeros:ones): "01" (1 zero, 2 ones is invalid), "0110" (2 zeros, 2 ones = 1:1 ≠ 1:2), but "01", "10", "011", "110" need checking. Actually valid ones are those where zeros*2 = ones*1.

Example 2 — Single Character

$ Input: s = "0", num1 = 1, num2 = 1

› Output: 0

💡 Note: Single '0' has ratio 1:0, but we need 1:1 ratio, so no valid substrings.

Example 3 — Multiple Valid Substrings

$ Input: s = "01011", num1 = 2, num2 = 3

› Output: 1

💡 Note: Only "01011" itself has 2 zeros and 3 ones, giving exact 2:3 ratio.

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of '0' and '1'
1 ≤ num1, num2 ≤ 100
gcd(num1, num2) = 1

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string and target ratio num1:num2

Process

Check each substring for exact ratio match

Output

Count of valid ratio substrings

Key Takeaway

🎯 Key Insight: Transform ratio checking into prefix sum difference tracking for O(n) efficiency

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is transforming the ratio problem into a prefix sum difference problem. Instead of checking ratios directly, we assign values to characters and use hash maps to count matching prefix sums. The optimal prefix sum approach runs in O(n) time with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(1)	Generate all possible substrings and check if each has the exact ratio
Prefix Sum with Hash Map	O(n)	O(n)	Transform ratio checking into difference tracking using prefix sums and hash map

Brute Force - Check All Substrings — Algorithm Steps

Step 1: For each starting index i from 0 to n-1
Step 2: For each ending index j from i to n-1, count zeros and ones
Step 3: Check if count0/count1 equals num1/num2 and increment result

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Start from each position and expand

Count 0s and 1s

Track zeros and ones in current substring

Check Ratio

Verify if counts match required ratio

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s, int num1, int num2) {
    int n = strlen(s);
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        int zeros = 0;
        int ones = 0;
        for (int j = i; j < n; j++) {
            if (s[j] == '0') {
                zeros++;
            } else {
                ones++;
            }
            
            // Check if ratio matches num1:num2 (zeros:ones)
            if (ones * num1 == zeros * num2) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char s[100001];
    int num1, num2;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    
    scanf("%d", &num1);
    scanf("%d", &num2);
    
    int result = solution(s, num1, num2);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested structure: n starting positions × n ending positions × n substring processing

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to count zeros and ones

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler