Alphabetical Sequence
Limits: 2 sec., 512 MiB
This statement was translated automatically from Ukrainian.
Zenyk and Marichka have a farm with \(n\) stallions. The horses on the farm have different coats — black, bay, dun, and others. There are \(26\) different coat colors in total, denoted by lowercase Latin letters.
Farmers lined up their stallions in a row. The row can be represented by a string \(s\) of \(n\) lowercase English letters, denoting the coat colors of the horses in the row.
Let’s call a sequence of horses alphabetical if the following two conditions are met simultaneously:
all horse coat colors in the sequence are distinct,
the letters denoting the horse coat colors, written in the order of the sequence, are in alphabetical order.
For example, the sequences abx, qrtu,
m are alphabetical, while the sequences aab,
qwerty are not.
You need to find the size of the longest contiguous subsegment of the given row of stallions that is an alphabetical sequence.
Input
The first line contains an integer \(n\) — the number of stallions in the row.
The second line contains a string \(s\) of \(n\) lowercase Latin letters, denoting the row of horses.
Output
Print a single integer — the size of the longest contiguous subsegment of the given row of stallions that is an alphabetical sequence.
Constraints
\(1 \le n \le 2 \cdot 10^5\).
Scoring consists of the following blocks:
1 point for each example from the statement,
5 points: \(s\) consists only of
acharacters,11 points: \(s\) consists only of
a,bcharacters,16 points: \(s\) consists only of
a,b,ccharacters,14 points: \(n \le 100\),
19 points: \(n \le 5000\),
33 points: no additional constraints.
You will receive the points for a block only if your solution passes all tests in that block.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 8 olympiad | 2 |
| Input (stdin) | Output (stdout) |
|---|---|
| 10 algotester | 3 |
Notes
In the first example, \(s =\)
olympiad. In this row, there are several subsegments of
length \(2\) that are alphabetical
sequences: ly, mp, ad. There are
no such subsegments of length greater than \(2\). Therefore, the answer is \(2\).
In the second example, \(s =\)
algotester. Here there are subsegments of length \(3\) that are alphabetical sequences:
got, est.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|