Each character of the English alphabet has been mapped to a digit as shown below.
A string is divisible if the sum of the mapped values of its characters is divisible by its length.
Given a string s, return the number of divisible substrings of s.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
| Substring | Mapped | Sum | Length | Divisible? |
|---|---|---|---|---|
| a | 1 | 1 | 1 | Yes |
| s | 7 | 7 | 1 | Yes |
| d | 2 | 2 | 1 | Yes |
| f | 3 | 3 | 1 | Yes |
| as | 1, 7 | 8 | 2 | Yes |
| sd | 7, 2 | 9 | 2 | No |
| df | 2, 3 | 5 | 2 | No |
| asd | 1, 7, 2 | 10 | 3 | No |
| sdf | 7, 2, 3 | 12 | 3 | Yes |
| asdf | 1, 7, 2, 3 | 13 | 4 | No |
Input: word = "asdf" Output: 6 Explanation: The table above contains the details about every substring of word, and we can see that 6 of them are divisible.
Example 2:
Input: word = "bdh" Output: 4 Explanation: The 4 divisible substrings are: "b", "d", "h", "bdh". It can be shown that there are no other substrings of word that are divisible.
Example 3:
Input: word = "abcd" Output: 6 Explanation: The 6 divisible substrings are: "a", "b", "c", "d", "ab", "cd". It can be shown that there are no other substrings of word that are divisible.
Constraints:
1 <= word.length <= 2000word consists only of lowercase English letters.Problem Overview: You get a lowercase string where each character maps to a numeric value from 1 to 9 based on predefined alphabet groups. A substring is divisible if the sum of its mapped values is divisible by the substring length. The task is to count all such substrings.
Approach 1: Enumeration (O(n²) time, O(1) space)
The most direct strategy is to enumerate every substring. Start an index i, extend the substring to every j ≥ i, and maintain the running sum of mapped character values. For each substring, compute its length len = j - i + 1 and check whether sum % len == 0. This avoids recomputing sums by updating the running total as the window expands. The approach is simple and useful for understanding the constraint, but the nested iteration leads to O(n²) time, which becomes slow for long strings.
Approach 2: Hash Table + Prefix Sum + Enumeration (O(n) time, O(n) space)
The key observation is that if a substring has length L and total value S, then it is divisible when S = k × L, where k is the average value of characters in that substring. Because each mapped value is between 1 and 9, the possible averages are also limited to 1 through 9. This allows enumeration over only 9 possible averages instead of all substring lengths.
Build a prefix sum array where prefix[i] is the total mapped value up to index i. For a chosen average k, rewrite the condition: prefix[j] - prefix[i] = k × (j - i). Rearranging gives prefix[j] - k × j = prefix[i] - k × i. This transforms the problem into counting equal values of prefix[x] - k × x. Use a hash table to store frequencies of these transformed values while scanning the string. For each position, look up how many previous indices share the same value and add that to the answer.
This technique combines prefix sums with hashing to convert a divisibility constraint into a frequency counting problem. The string is processed nine times (for averages 1–9), which keeps the overall complexity O(9n) ≈ O(n) with O(n) auxiliary space.
Recommended for interviews: Start by explaining the enumeration solution to demonstrate you understand the substring condition. Then move to the optimized hash-table + prefix-sum method. Interviewers typically expect this improvement because it reduces quadratic enumeration to linear scanning using a classic prefix transformation technique commonly seen in string and prefix-sum problems.
First, we use a hash table or array mp to record the number corresponding to each letter.
Then, we enumerate the starting position i of the substring, and then enumerate the ending position j of the substring, calculate the numerical sum s of the substring s[i..j]. If s can be divided by j-i+1, then a divisible substring is found, and the answer is increased by one.
After the enumeration is over, return the answer.
The time complexity is O(n^2), and the space complexity is O(C). Where n is the length of the string word, and C is the size of the character set, in this question C=26.
Similar to Solution 1, we first use a hash table or array mp to record the number corresponding to each letter.
If the sum of the numbers in an integer subarray can be divided by its length, then the average value of this subarray must be an integer. And because the number of each element in the subarray is in the range of [1, 9], the average value of the subarray can only be one of 1, 2, cdots, 9.
We can enumerate the average value i of the subarray. If the sum of the elements in a subarray can be divided by i, suppose the subarray is a_1, a_2, cdots, a_k, then a_1 + a_2 + cdots + a_k = i times k, that is, (a_1 - i) + (a_2 - i) + cdots + (a_k - i) = 0. If we regard a_k - i as a new element b_k, then the original subarray becomes b_1, b_2, cdots, b_k, where b_1 + b_2 + cdots + b_k = 0. We only need to find out how many subarrays in the new array have an element sum of 0, which can be implemented with "hash table" combined with "prefix sum".
The time complexity is O(10 times n), and the space complexity is O(n). Here, n is the length of the string word.
| Approach | Complexity |
|---|---|
| Enumeration | — |
| Hash Table + Prefix Sum + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumeration | O(n²) | O(1) | Small inputs or when demonstrating the basic substring logic |
| Hash Table + Prefix Sum + Average Enumeration | O(n) | O(n) | Optimal solution for large strings; converts divisibility condition into prefix frequency counting |
leetcode-2950 Number of Divisible Substrings - partial sum+decoupling+linear-time • Code-Yao • 417 views views
Watch 2 more video solutions →Practice Number of Divisible Substrings with our built-in code editor and test cases.
Practice on FleetCode