Leetcode Problem 2489. Number of Substrings With Fixed Ratio

2489. Number of Substrings With Fixed Ratio

Leetcode Solutions

Hashmap using Prefix Counts

  1. Initialize a hashmap to store the frequency of each difference encountered and set the frequency of difference 0 to 1 (to account for the whole string being a valid substring).
  2. Initialize variables to keep track of the running count of 0s and 1s.
  3. Iterate through the string s. a. If the current character is 0, increment the count of 0s; otherwise, increment the count of 1s. b. Calculate the current difference as count_0s * num2 - count_1s * num1. c. If the current difference is in the hashmap, increment the answer by the frequency of this difference. d. Update the hashmap with the new frequency of the current difference.
  4. Return the answer.
UML Thumbnail

Brute Force with Prefix Sums

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...