A calibration rig at a sensor-assembly plant burns a numeric code — a string made only of the digits '0' through '9' — onto every metal plate it produces. During an audit, an inspector studies every contiguous window of the code (every contiguous substring) and calls a window balanced when each distinct digit appearing inside it occurs exactly as many times as every other distinct digit appearing inside it. (A window built from only one distinct digit is always balanced, no matter how long it is, since there is no other digit to compare it against.) Two windows that read as the exact same sequence of digits are considered the same window even if they came from different positions in the code. Given the code, count how many textually distinct balanced windows it contains.
s, a string made up of the characters '0'-'9'.s.s <= 20s consists only of the characters '0' through '9'.Example 1
Input
1212
Expected
5
Explanation
The distinct substrings of 1212 are 1, 2, 12, 21, 121, 212, and 1212. Checking each: 1, 2, 12, 21, and 1212 are balanced (each distinct digit that appears occurs the same number of times as every other), while 121 (digit 1 appears twice, digit 2 once) and 212 (digit 2 appears twice, digit 1 once) are not. That leaves 5 balanced windows: 1, 2, 12, 21, 1212.
Example 2
Input
12321
Expected
9
Explanation
The balanced windows are 1, 2, 3, 12, 23, 32, 21, 123, and 321 — nine in total. Windows such as 1232, 12321, 232, and 2321 are not balanced because inside them one digit occurs more often than another (for example, 12321 has digits 1 and 2 twice each but digit 3 only once).
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →