Pieces with a Whole Average Weight

Medium

On an old phone keypad the letters are spread over nine keys, and the weight of a letter is the number of its key: | Key | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |---|---|---|---|---|---|---|---|---|---| | Letters | ab | cde | fgh | ijk | lmn | opq | rst | uvw | xyz | You are given a string text. Consider all of its non-empty contiguous pieces (equal pieces at different positions count separately). A piece is good if the total weight of its letters divides evenly by its length, that is, the average letter weight in the piece is a whole number. Return the number of good pieces.

Example 1

text='bdh' → 4

Weights: b = 1, d = 2, h = 3. The single letters "b", "d", "h" qualify, and so does "bdh": sum 6, length 3, average 2. "bd" (3 / 2) and "dh" (5 / 2) have fractional averages. 4 in total.

Example 2

text='az' → 3

a = 1, z = 9: the sum 10 divides by 2, so "a", "z" and "az" all qualify.

Example 3

text='mop' → 4

Constraints

1 ≤ text.length ≤ 2000
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Counting Prefix Sum

Similar problems

Separate Two Words by Letters Medium Pieces With Matching Ends Medium Matching Ends per Range Medium Pump Rods at Their Peak Hard A Hint for a Digit Guess Medium

Input

text='bdh'

Expected

Run checks the first 3 tests in your browser. Submit checks all 93 tests on the server, hidden ones included.