AIOC Banner

Problem: Medusa's Snakes

Want to try solving this problem? You can submit your code online if you log in or register.


Medusa's Snakes

Input File: snakein.txt
Output File: snakeout.txt
Time Limit: 1 second
Memory Limit: 1 GB

After the success of your latest research project in mythical DNA, you have gained the attention of a most diabolical creature: Medusa.

Medusa has snakes instead of hair. Each of her snakes' DNA is represented by an uppercase string of letters. Each letter is one of S, N, A, K or E.

Your extensive research shows that a snake's venom level depends on its DNA. A snake has venom level x if its DNA:

For example, a snake with venom level 1 has DNA SNAKE, while a snake that has venom level 3 has DNA SSSNNNAAAKKKEEE. If a snake's DNA does not fit the format described above, it has a venom level of 0.

Medusa would like your help making her snakes venomous, by deleting zero or more letters from their DNA. Given a snake's DNA, can you work out the maximum venom level this snake could have?

Input

The first line contains the integer N: the number of letters in the snake's DNA. The second line contains a string of N uppercase letters, representing the snake's DNA. Each letter is one of S, N, A, K or E.

Output

Your program should output a single integer: the maximum venom level the snake could have, after you delete some (possibly none) of the letters from its DNA.

Sample Input 1

17
KSEESNANNAAKNKESE

Sample Output 1

2

Sample Input 2

22
SSSSNNNAAAAKKKKEEEEEEE

Sample Output 2

3

Sample Input 3

15
SNAKESNAKESNAKE

Sample Output 3

1

Sample Input 4

6
KANSAS

Sample Output 4

0

Explanation

The letters that are deleted in each case are underlined below:

Subtasks & Constraints

For all cases, 5 ≤ N ≤ 100,000. Additionally:

 


Privacy statement
© Australian Mathematics Trust 2001-2021

Contact: training@orac.amt.edu.au
Page generated: 28 November 2021, 10:13pm AEDT