Ahmed loves the letter "Z" very much, and he loves the number of "Z" letters in each string s.
Input
The first line of input contains string s.
Output
Print an integer representing the number of occurrences of the letter "Z". If there is no "Z", type "NO" without the quotes. examples: input:
zzzz
output: 4
input:
codeforces
output:
NO
Auto comment: topic has been updated by mzaferbooshi96 (previous revision, new revision, compare).
Auto comment: topic has been updated by mzaferbooshi96 (previous revision, new revision, compare).
I think this can be solved with topological sorting and DP.
Notice that we can represent the string as a Directed Acyclic Graph (DAG), where each node has a character and an edge to the next node. I think that each node $$$i$$$ has a directed edge to node $$$i + 1$$$, but I don't know how to prove it. Now we topologically sort the graph and perform dynamic programming. Let $$$dp_i$$$ represent the number of letters Z at node $$$i$$$. The transitions are trivial.
Our answer is $$$dp_n$$$. If $$$dp_n$$$ is equal to $$$0$$$, we print "NO".
I hope this helped.