Skip to content

2489. Number of Substrings With Fixed Ratio 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  long long fixedRatio(string s, int num1, int num2) {
    // Let x := the number of 0s and y := the number of 1s in the subarray.
    // We want x : y = num1 : num2, so our goal is to find number of subarrays
    // with x * num2 - y * num1 = 0. To achieve this, we can use a prefix count
    // map to record the count of the running x * num2 - y * num1. If the
    // running x * num2 - y * num1 = prefix, then add count[prefix] to the
    // `ans`.
    long ans = 0;
    long prefix = 0;
    unordered_map<long, int> prefixCount{{0, 1}};

    for (const char c : s) {
      if (c == '0')
        prefix += num2;
      else  // c == '1'
        prefix -= num1;
      ans += prefixCount[prefix];
      ++prefixCount[prefix];
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public long fixedRatio(String s, int num1, int num2) {
    // Let x := the number of 0s and y := the number of 1s in the subarray.
    // We want x : y = num1 : num2, so our goal is to find number of subarrays
    // with x * num2 - y * num1 = 0. To achieve this, we can use a prefix count
    // map to record the count of the running x * num2 - y * num1. If the
    // running x * num2 - y * num1 = prefix, then add count[prefix] to the
    // `ans`.
    long ans = 0;
    long prefix = 0;
    Map<Long, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0L, 1);

    for (final char c : s.toCharArray()) {
      if (c == '0')
        prefix += num2;
      else // c == '1'
        prefix -= num1;
      ans += prefixCount.getOrDefault(prefix, 0);
      prefixCount.merge(prefix, 1, Integer::sum);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def fixedRatio(self, s: str, num1: int, num2: int) -> int:
    # Let x := the number of 0s and y := the number of 1s in the subarray.
    # We want x : y = num1 : num2, so our goal is to find number of subarrays
    # with x * num2 - y * num1 = 0. To achieve this, we can use a prefix count
    # map to record the count of the running x * num2 - y * num1. If the
    # running x * num2 - y * num1 = prefix, then add count[prefix] to the
    # `ans`.
    ans = 0
    prefix = 0
    prefixCount = collections.Counter({0: 1})

    for c in s:
      if c == '0':
        prefix += num2
      else:  # c == '1'
        prefix -= num1
      ans += prefixCount[prefix]
      prefixCount[prefix] += 1

    return ans