Number of Divisible Substrings - Solution & Explanation

Q: Is Number of Divisible Substrings easy or hard?

The problem is rated Medium because the brute force idea is simple but inefficient. Recognizing the mathematical transformation with prefix sums and limiting averages to 1–9 requires algorithmic insight, which is typical of medium-level interview problems.

Q: Number of Divisible Substrings Python/Java solution

Most implementations compute prefix sums of mapped character values and then iterate over averages 1 through 9. A hash map stores counts of prefix[i] - k*i values to detect valid substrings in O(n) time. The same logic translates cleanly to Python, Java, C++, and Go.

Q: How to solve Number of Divisible Substrings in O(n)?

Use a prefix sum of mapped character values and iterate through possible averages from 1 to 9. For each average k, compute the transformed value prefix[i] - k*i and store frequencies in a hash map. Matching values indicate substrings whose sums equal k times their length, which satisfies the divisibility condition.

Q: What is the best approach for Number of Divisible Substrings?

The most efficient method uses a hash table combined with prefix sums. By enumerating possible average values from 1 to 9 and transforming the equation to prefix[j] - k*j = prefix[i] - k*i, the problem becomes counting equal prefix states using a hash map. This reduces the complexity to O(n) time and O(n) space.

Q: Is Number of Divisible Substrings asked at Google/Amazon/Meta?

Problems involving prefix sums, substring enumeration, and hash map frequency counting frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying technique of transforming substring conditions using prefix sums is commonly tested.

Q: What data structure is used in Number of Divisible Substrings?

The optimized solution relies mainly on a hash table to store counts of transformed prefix values. It also uses a prefix sum array to compute substring sums efficiently while processing the string sequentially.

Q: What is the time complexity of Number of Divisible Substrings?

The brute force enumeration approach runs in O(n²) time because every substring is checked. The optimized solution with hash table and prefix sum runs in O(n) time since the string is scanned a constant number of times (nine averages). Space complexity for the optimized version is O(n).

MediumPremiumFree on FleetCodeHash Table String Counting Prefix Sum19 min readAsked at: IBM, Paytm, Amdocs +1

Practice this problem

Problem Statement

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 <= 2000
word consists only of lowercase English letters.

Approach Overview

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.

Approach 1: Enumeration

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.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Approach 2: Hash Table + Prefix Sum + Enumeration

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.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Enumeration	—
Hash Table + Prefix Sum + Enumeration	—

Detailed Complexity Analysis

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

Video Solution

leetcode-2950 Number of Divisible Substrings - partial sum+decoupling+linear-time • Code-Yao • 424 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Number of Divisible Substrings easy or hard?

The problem is rated Medium because the brute force idea is simple but inefficient. Recognizing the mathematical transformation with prefix sums and limiting averages to 1–9 requires algorithmic insight, which is typical of medium-level interview problems.

Number of Divisible Substrings Python/Java solution

Most implementations compute prefix sums of mapped character values and then iterate over averages 1 through 9. A hash map stores counts of prefix[i] - k*i values to detect valid substrings in O(n) time. The same logic translates cleanly to Python, Java, C++, and Go.

How to solve Number of Divisible Substrings in O(n)?

Use a prefix sum of mapped character values and iterate through possible averages from 1 to 9. For each average k, compute the transformed value prefix[i] - k*i and store frequencies in a hash map. Matching values indicate substrings whose sums equal k times their length, which satisfies the divisibility condition.

What is the best approach for Number of Divisible Substrings?

The most efficient method uses a hash table combined with prefix sums. By enumerating possible average values from 1 to 9 and transforming the equation to prefix[j] - k*j = prefix[i] - k*i, the problem becomes counting equal prefix states using a hash map. This reduces the complexity to O(n) time and O(n) space.

Is Number of Divisible Substrings asked at Google/Amazon/Meta?

Problems involving prefix sums, substring enumeration, and hash map frequency counting frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying technique of transforming substring conditions using prefix sums is commonly tested.

What data structure is used in Number of Divisible Substrings?

The optimized solution relies mainly on a hash table to store counts of transformed prefix values. It also uses a prefix sum array to compute substring sums efficiently while processing the string sequentially.

What is the time complexity of Number of Divisible Substrings?

The brute force enumeration approach runs in O(n²) time because every substring is checked. The optimized solution with hash table and prefix sum runs in O(n) time since the string is scanned a constant number of times (nine averages). Space complexity for the optimized version is O(n).

Ready to solve this problem?

Practice Number of Divisible Substrings with our built-in code editor and test cases.

Practice on FleetCode

Count Substrings Divisible By Last Digit

Problem Info

DifficultyMedium

Acceptance74.6%

Approaches2

Reading time19 min

Asked at

IBM Paytm Amdocs Wayfair

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Enumeration

Code

Approach 2: Hash Table + Prefix Sum + Enumeration

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents