NOI Contest Archive

Archive / 2021 / December 2021

The King’s Court

Medium · National Olympiad in Informatics Sri Lanka - December 2021

The King Willoughby is known throughout the realm for his virtue and righteousness. Though this is not the case for the King’s court filled with greedy and vicious men vying to earn the King’s good faith for their own benefit. King Willoughby is no ignorant man. He uses an untold pigeonhole to distinguish the good and the vile. The wise men are ranked using Latin letters, with ‘a’ regarded as the most faithful of men.

On a given day, the wise men of the King’s court consist of string s which amount to ** S **.

As the King’s trusted squire, he instructs you to bring forth the most faithful men present in the court that day. You have to successively dismiss the vile men present in an imperceptible manner.

Therefore, you are instructed to choose any wise man denoted by index i and dismiss him, if at least one of the adjacent members are one rank more faithful. With each dismissal the number of wise men are decreases by one and the index i should be **1 \(\leq\) i \(\leq\) S **.

For the member Si, the adjacent members are Si-1 and Si+1 and the first and last members have only one adjacent member.

Example,

If the number of wise men present in the court was 5 and they are denoted as edfed.

  1. Firstly you can dismiss the member S1 denoted by e as the adjacent member, S2 is denoted as d. Indicating him to be one rank more faithful,

Then the wise men become, dfed

  1. Successively, you can dismiss the member S2 denoted by f. As the adjacent member, S3 is denoted as e. Indicating him to be one rank more faithful,

Then the wise men present becomes, ded

  1. Finally the member S2 denoted by e is dismissed as, the member S3 is denoted as d.

It is evident that no more dismissals can be performed and the King will only summon the remainder of the wise men.

Find the maximum number of members you can dismiss to find the most faithful of men.

Input Format

The first line of input should consist of the number of wise men present in the court on the given date - ** S **

The second line of input consists of the string of wise men present denoted by lowercase Latin letters.

Output Format

An integer representing maximum possible number of members who can be dismissed.

Constraints

1 \(\leq\) ** S ** \(\leq\) 100
** S ** - Length of the string S

Sample Input 0

8
edfdefde

Sample Output 0

4

Open on HackerRank ↗ · Markdown source · Back to the archive