Maximum Deletions on a String
You are given a string s consisting of only lowercase English letters. In one operation, you can:
- Delete the entire string
s, or - Delete the first
iletters ofsif the firstiletters ofsare equal to the followingiletters ins, for anyiin the range1 <= i <= s.length / 2.
Return the maximum number of operations needed to delete all of s.
Example 1
Input
s = "abcabcdabc"Output
2Delete the first 3 letters because the next 3 letters are equal, then delete all remaining letters, for a maximum of 2 operations.
Example 2
Input
s = "aaabaab"Output
4By deleting "a", then "aab", then "a", and finally all remaining letters, the string can be deleted in a maximum of 4 operations.
Constraints
- 1 <= s.length <= 4000
- s consists only of lowercase English letters.