Peel Off a Repeated Start

Hard

You get a string text of lowercase English letters. In one move you may: - erase the whole string; - or erase the first i letters if the very next i letters are the same (1 ≤ i ≤ len(text) / 2). For example, in "cdcde" you may erase the start "cd" because "cd" follows right after it, leaving "cde". Return the largest number of moves in which the string can be erased completely.

Example 1

text="xyxyz" → 2

Peel off "xy" (it is followed by "xy" again) to get "xyz", then erase the rest. Two moves.

Example 2

text="bbbb" → 4

Peel off one "b" three times, then erase the last one with the fourth move.

Example 3

text="abcab" → 1

No prefix is immediately repeated, so the only move is to erase the whole string.

Constraints

1 ≤ len(text) ≤ 4000
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming String Matching Hash Function Rolling Hash

Similar problems

Phrase From Word Beginnings, Long Edition Hard Target From Word Beginnings Medium Palindrome by Adding Letters in Front Hard Mirror Chunk Split Hard Start That Matches the End Hard

Input

text="xyxyz"

Expected

Run checks the first 3 tests in your browser. Submit checks all 106 tests on the server, hidden ones included.