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 ofnon-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.

Examples

Example 1:

1
2
3
4
5
6
7
8


Input: s = "0110011", num1 = 1, num2 = 2
Output: 4
Explanation: There exist 4 non-empty ratio substrings.
- The substring s[0..2]: "_011_ 0011". It contains one 0 and two 1's. The ratio is 1 : 2.
- The substring s[1..4]: "0 _110_ 011". It contains one 0 and two 1's. The ratio is 1 : 2.
- The substring s[4..6]: "0110 _011_ ". It contains one 0 and two 1's. The ratio is 1 : 2.
- The substring s[1..6]: "0 _110011_ ". It contains two 0's and four 1's. The ratio is 2 : 4 == 1 : 2.
It can be shown that there are no more ratio substrings.

Example 2:

1
2
3


Input: s = "10101", num1 = 3, num2 = 1
Output: 0
Explanation: There is no ratio substrings of s. We return 0.

Constraints:

1 <= s.length <= 10^5
1 <= num1, num2 <= s.length
num1 and num2 are coprime integers.

Solution

Method 1 – Prefix Hashing and Counting

Intuition

For a substring s[l..r], let c0 = number of 0’s, c1 = number of 1’s. The substring is valid if c0:num1 == c1:num2, i.e., c0num2 == c1num1. We can use prefix sums and a hash map to count the number of valid substrings ending at each position.

Approach

For each prefix, keep track of (num2 * count_0 - num1 * count_1).
For each position, the number of previous prefixes with the same value gives the number of valid substrings ending here.
Use a hash map to count occurrences of each prefix value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include <unordered_map>
class Solution {
public:
    int fixedRatioSubstrings(string s, int num1, int num2) {
        unordered_map<int, int> count;
        count[0] = 1;
        int c0 = 0, c1 = 0, ans = 0;
        for (char ch : s) {
            if (ch == '0') c0++;
            else c1++;
            int key = num2 * c0 - num1 * c1;
            ans += count[key];
            count[key]++;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func fixedRatioSubstrings(s string, num1, num2 int) int {
    count := map[int]int{0: 1}
    c0, c1, ans := 0, 0, 0
    for _, ch := range s {
        if ch == '0' { c0++ } else { c1++ }
        key := num2*c0 - num1*c1
        ans += count[key]
        count[key]++
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


import java.util.*;
class Solution {
    public int fixedRatioSubstrings(String s, int num1, int num2) {
        Map<Integer, Integer> count = new HashMap<>();
        count.put(0, 1);
        int c0 = 0, c1 = 0, ans = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '0') c0++;
            else c1++;
            int key = num2 * c0 - num1 * c1;
            ans += count.getOrDefault(key, 0);
            count.put(key, count.getOrDefault(key, 0) + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    fun fixedRatioSubstrings(s: String, num1: Int, num2: Int): Int {
        val count = mutableMapOf(0 to 1)
        var c0 = 0; var c1 = 0; var ans = 0
        for (ch in s) {
            if (ch == '0') c0++ else c1++
            val key = num2 * c0 - num1 * c1
            ans += count.getOrDefault(key, 0)
            count[key] = count.getOrDefault(key, 0) + 1
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def fixedRatioSubstrings(self, s: str, num1: int, num2: int) -> int:
        from collections import defaultdict
        count = defaultdict(int)
        count[0] = 1
        c0 = c1 = ans = 0
        for ch in s:
            if ch == '0':
                c0 += 1
            else:
                c1 += 1
            key = num2 * c0 - num1 * c1
            ans += count[key]
            count[key] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


use std::collections::HashMap;
impl Solution {
    pub fn fixed_ratio_substrings(s: String, num1: i32, num2: i32) -> i32 {
        let mut count = HashMap::new();
        count.insert(0, 1);
        let (mut c0, mut c1, mut ans) = (0, 0, 0);
        for ch in s.chars() {
            if ch == '0' { c0 += 1; } else { c1 += 1; }
            let key = num2 * c0 - num1 * c1;
            ans += *count.get(&key).unwrap_or(&0);
            *count.entry(key).or_insert(0) += 1;
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
    fixedRatioSubstrings(s: string, num1: number, num2: number): number {
        const count = new Map<number, number>()
        count.set(0, 1)
        let c0 = 0, c1 = 0, ans = 0
        for (const ch of s) {
            if (ch === '0') c0++
            else c1++
            const key = num2 * c0 - num1 * c1
            ans += count.get(key) ?? 0
            count.set(key, (count.get(key) ?? 0) + 1)
        }
        return ans
    }
}

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(n)

Problem#

Examples#

Solution#

Method 1 – Prefix Hashing and Counting#

Intuition#

Approach#

Code#

Complexity#