STRINGGRAFT

View as PDF

Submit solution


Points: 0.01 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

A single string is a string consisting of ~1~ character, with a length equal to the position of that character in the alphabet. For example:

  • a, bb, dddd are valid single strings.

  • ab, aa, bbbb are not single strings.

A grafted string is a string composed of multiple single strings concatenated together, and the preceding single string must have a character that is less than the character of the following single string. For example:

  • a, abb, adddd are valid grafted strings.

  • bba, aabb, bbbb are not grafted strings.

Given a string ~s~ consisting of lowercase letters, find the longest subsequence (not necessarily contiguous) in ~s~ that is a grafted string. Output the length of that string.

Input

A single line containing the string ~s~ ~(|s| \leq 10^5)~.

Output

Output the length of the longest subsequence that satisfies the problem statement.

Scoring

Subtask Points Limits
1 ~20\%~ ~|s| \leq 20~
2 ~30\%~ ~|s| \leq 5000~
3 ~50\%~ No additional limits.

Sample Input 1

adddebbaacccd

Sample Output 1

6

Sample Input 2

abbcdccddd

Sample Output 2

7

Notes

In example ~1~: The longest grafted string in the example test is abbccc.

In example ~2~: The longest grafted string in the example test is abbdddd.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.