Strings Hate Zeroes
Tag(s):

## Medium-Hard

Problem
Editorial
Analytics

Consider a string $s$ of length $n$ consisting of characters $0$ to $9$. Let $r(s)$ be the number of distinct characters this string has, and $N(c)$ be the number of times character $c$ appears in the string. We call the string $s$ happy if $N(0) \lt \frac{n}{r(s)}$

For example strings $010$ and $012$ are NOT happy, but strings $0112$ and $123456789$ are happy.

Given a string $S$, find the number of happy substrings(out of a total $\frac{|S|(|S|+1)}{2}$ ) of $S$.

Input
The only line of the input contains the string $S$

Output
Print one line containing the number of happy substrings of $S$

Constraints

• $|S| \le 10^5$
SAMPLE INPUT
011
SAMPLE OUTPUT
4
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

ICPC de Tryst

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Probablity
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Math > Combinatorics