Evenly Mixed Digit Pieces

Medium

You are given a string digits made of decimal digits. Call a substring **even** if every digit that occurs in it occurs the same number of times. For example, "1221" and "507" are even, while "1121" is not. Return the number of **distinct** even substrings of digits. Equal substrings found at different positions are counted once.

Example 1

digits='3443' → 6

The pieces that work are "3", "4", "34", "44" (a single digit twice is fine), "43" and "3443" (two 3s and two 4s). "344" and "443" do not. That makes 6.

Example 2

digits='777' → 3

Every substring is all 7s, but only three are distinct: "7", "77" and "777".

Example 3

digits='120' → 6

Constraints

1 ≤ digits.length ≤ 2000
digits consists of the digits 0–9 only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Counting Hash Function Rolling Hash

Similar problems

Recurring Gene Windows Medium Every Bit Pattern Inside Medium Two Words One Letter Apart Medium A Hint for a Digit Guess Medium Characters Grouped by Count Medium

Input

digits='3443'

Expected

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