Number of substrings with fixed ratio

Hash Table Math String Prefix Sum

57.0% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn fixed_ratio(s: String, num1: i32, num2: i32) -> i64 {
    let mut map: HashMap<i64, i64> = HashMap::new();
    map.insert(0, 1);
    let mut count0 = 0i64;
    let mut count1 = 0i64;
    let mut ans = 0i64;
    let n1 = num1 as i64;
    let n2 = num2 as i64;
    for ch in s.bytes() {
      if ch == b'0' { count0 += 1; } else { count1 += 1; }
      let key = count0 * n2 - count1 * n1;
      if let Some(&c) = map.get(&key) {
        ans += c;
      }
      *map.entry(key).or_insert(0) += 1;
    }
    ans
  }
}