mzaferbooshi96's blog

By mzaferbooshi96, history, 2 hours ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mzaferbooshi96 (previous revision, new revision, compare).

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mzaferbooshi96 (previous revision, new revision, compare).

»
2 hours ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

  • »
    »
    114 minutes ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    My implementation