Number of Divisible Substrings Solution


class Solution:
    def countDivisibleSubstrings(self, word: str) -> int:
        ans = 0

        def f(c: str) -> int:
            return 9 - (ord('z') - ord(c)) // 3

        for avg in range(1, 10):
            prefix = 0
            prefixCount = collections.Counter({0: 1})
            for c in word:
                prefix += f(c) - avg
                ans += prefixCount[prefix]
                prefixCount[prefix] += 1

        return ans

Problem Description

The “Number of Divisible Substrings” problem on LeetCode is about finding substrings that can be evenly divided based on their character values. Imagine you’re at a party, trying to split the bill evenly among friends. You need to find all groups of friends (substrings) that can share the bill (be divisible) without anyone feeling left out.

Given a string word consisting of lowercase letters, your task is to count the number of substrings that satisfy a specific condition based on the average of their character values. The character values are derived from their positions in the alphabet, and you need to check if the sum of these values divided by the number of characters equals an integer in the range of 1 to 9.

Approach

The solution involves calculating a prefix sum based on character values derived from the string. For each character, we compute its value using the function f(c), which maps characters to values between 1 and 9. We iterate through possible averages (from 1 to 9) and maintain a count of prefix sums using a counter. The key idea is to check how many times a particular prefix sum has occurred, which helps in determining the number of valid substrings.

Time and Space Complexity

Complexity Type Complexity
Time Complexity O(n)
Space Complexity O(n)

Real-World Example

Imagine you’re at a potluck dinner, and everyone brings a dish. You want to find out how many combinations of dishes can be shared evenly among your friends. Each dish has a certain “value” based on how much everyone likes it. The task is to find all combinations of dishes (substrings) that can be shared evenly (divisible by the average value). This problem illustrates how we can group things based on shared characteristics!

Similar Problems