Show problems as
Classic problem #2950MediumHash TableStringCountingPrefix Sum

Number of Divisible Substrings

Real-world version: Stretches Whose Total Divides Their Length
Tracked in this browser only
Read Number of Divisible Substrings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Every lowercase letter carries a number. The first three letters carry 1, the next three carry 2, and so on in groups of three, so the last group, holding only y and z, carries 9.

A stretch of neighbouring letters is even-handed when the total of its letters' numbers divides exactly by how many letters the stretch holds.

Return how many even-handed stretches the word word holds.

Examples

Example 1

Input
word = "az"
Output
3

Each letter on its own is even-handed, and together they total 10 across two letters, which divides evenly.

Example 2

Input
word = "zzz"
Output
6

Every letter carries 9, so every stretch totals nine times its own length.

Example 3

Input
word = "abz"
Output
5

The three single letters count, and so do the first two together totalling 2 and the last two totalling 10. All three together total 11, which three does not divide.

Constraints

  • 1 <= word.length <= 2000
  • word holds only lowercase English letters

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_divisible_substrings(word: str) -> int:
Java
public int countDivisibleSubstrings(String word)

More on the same topics