Strange Editor
Time limit1.5sMemory limit256 MB
Find the fewest push, pop, and paste operations needed to write string S (length up to 2000) with a stack-based editor.
- Level
Medium7 of 10
- Topics
- Dynamic programming, String
- Solved
- No attempts yet
Problem
Bru is writing text with a very inefficient editor. Bru wants to write the text he needs with this editor.
The editor has a temporary storage space called a stack, and the text is written using this stack. The editor supports only three operations.
- Push one character onto the back of the stack.
- Pop the last character from the stack. If the stack is empty, nothing happens.
- Paste the string stored in the stack into the text. The stack stays the same after this operation.
For Bru, compute the minimum number of operations needed to write the desired text. After the text is complete, the stack does not need to be empty.
Input
The first line contains the text S that Bru wants to write with the editor. (1 ≤ |S| ≤ 2000)
S consists only of lowercase English letters.
Output
Print the minimum number of operations Bru must perform to write the text.