Dynamic Input Tool
Time limit2sMemory limit512 MB
Find the minimum number of append-character and append-subsequence-of-current-string operations needed to build a given string from empty.
- Level
Hard8 of 10
- Topics
- Dynamic programming, String, Greedy, Binary search
- Solved
- No attempts yet
Problem
CodingSlave 1.0 is a brand new text editor. There are two operations you can use to compose a string in CodingSlave 1.0:
- Add one character at the end of the current string.
- Choose a nonempty subsequence of the current string and add it at the end of the current string.
Initially, the current string is empty.
Given a word consisting of lowercase English letters, find the minimum number of operations needed to compose this string.
Input
The first line contains a string consisting of lowercase English letters ().
Output
Print one integer: the minimum number of operations needed to compose using CodingSlave 1.0.