Problem: Medusa's Snakes
Want to try solving this problem? You can submit your code online if you log in or register.
Input File: snakein.txt
Output File: snakeout.txt
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:
- has exactly 5x letters
- begins with x copies of the letter S
- then has x copies of the letter N
- then has x copies of the letter A
- then has x copies of the letter K
- ends with x copies of the letter E.
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?
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
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
Sample Output 1
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3
Sample Input 4
Sample Output 4
The letters that are deleted in each case are underlined below:
- Sample Input 1: KSEESNANNAAKNKESE → SSNNAAKKEE.
- Sample Input 2: SSSSNNNAAAAKKKKEEEEEEE → SSSNNNAAAKKKEEE.
- Sample Input 3: SNAKESNAKESNAKE → SNAKE.
- Sample Input 4: No matter which letters you delete, the snake will always have venom level 0, so the answer is 0.
Subtasks & Constraints
For all cases, 5 ≤ N ≤ 100,000. Additionally:
- For Subtask 1 (15 marks), all S come before all N, which come before all A, which come before
all K, which come before all E. There will be at least one of each letter. Sample Input 2 is an example of a case that could be in this subtask.
- For Subtask 2 (15 marks), the DNA sequence consists of SNAKE repeated some number of
times. Sample Input 3 is an example of a case that could be in this subtask.
- For Subtask 3 (30 marks), N ≤ 10.
- For Subtask 4 (20 marks), N ≤ 1000.
- For Subtask 5 (20 marks), no further constraints apply.