Number of Divisible Substrings Solution in Java

Ah, the classic “Number of Divisible Substrings” problem! It’s like trying to find a needle in a haystack, but instead of a needle, you’re looking for substrings that are divisible by a number. Imagine you’re at a party, and everyone is trying to find a partner to dance with. But instead of just any partner, they want someone who can do the cha-cha in perfect sync. That’s what this problem is all about—finding those special substrings that meet the criteria!

Links to Other Solutions

Language	Link
C++ Solution	View Solution
Python Solution	View Solution

Code Solution


class Solution {
  public int countDivisibleSubstrings(String word) {
    int ans = 0;

    for (int avg = 1; avg <= 9; ++avg) {
      int prefix = 0;
      Map prefixCount = new HashMap<>();
      prefixCount.put(0, 1);
      for (final char c : word.toCharArray()) {
        prefix += f(c) - avg;
        ans += prefixCount.getOrDefault(prefix, 0);
        prefixCount.merge(prefix, 1, Integer::sum);
      }
    }

    return ans;
  }

  private int f(char c) {
    return 9 - ('z' - c) / 3;
  }
}

Approach Explanation

The approach taken in this solution is quite clever. It uses a prefix sum technique to keep track of the cumulative values of the characters in the string. For each character, it calculates a prefix sum adjusted by the average value (from 1 to 9). The key here is to maintain a count of how many times each prefix sum has occurred, allowing us to efficiently count the number of valid substrings that meet the criteria.

Time and Space Complexity

Time Complexity: O(n * 9) = O(n), where n is the length of the string. We iterate through the string for each average value from 1 to 9.

Space Complexity: O(n) in the worst case for the prefix count map, which stores the frequency of prefix sums.

Real-World Example

Imagine you’re at a buffet, and you can only take a certain number of dishes that are divisible by your favorite number (let’s say 3). You start counting the dishes you take, and every time you reach a total that’s divisible by 3, you do a little happy dance. This problem is similar; you’re counting substrings that meet a specific average condition, just like counting your favorite dishes!