#2430

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Deletions on a String

Find the maximum number of deletions on a string using state transition dynamic programming and rolling hash techniques efficiently.

string dynamic programming rolling hash string matching hash function

Problem Statement

You are given a string s containing only lowercase English letters. In one operation, you may delete the first k characters if the substring of length k starting at the beginning equals the next k characters immediately following it.

Return the maximum number of operations required to delete all characters of s. For instance, if s = "ababc", you can delete "ab" first because it matches the next "ab", resulting in "abc", and continue until the string is empty.

Examples

Example 1

Input: s = "abcabcdabc"

Output: 2

Delete the first 3 letters ("abc") since the next 3 letters are equal. Now, s = "abcdabc".
Delete all the letters. We used 2 operations so return 2. It can be proven that 2 is the maximum number of operations needed. Note that in the second operation we cannot delete "abc" again because the next occurrence of "abc" does not happen in the next 3 letters.

Example 2

Input: s = "aaabaab"

Output: 4

Delete the first letter ("a") since the next letter is equal. Now, s = "aabaab".
Delete the first 3 letters ("aab") since the next 3 letters are equal. Now, s = "aab".
Delete the first letter ("a") since the next letter is equal. Now, s = "ab".
Delete all the letters. We used 4 operations so return 4. It can be proven that 4 is the maximum number of operations needed.

Example 3

Input: s = "aaaaa"

Output: 5

In each operation, we can delete the first letter of s.

Constraints

1 <= s.length <= 4000
s consists only of lowercase English letters.

Solution Approach

Dynamic Programming with Prefix Matching

Create a dp array where dp[i] represents the maximum deletions possible for s[i:]. Iterate from the end toward the start, and for each i, try all lengths of k where s[i:i+k] matches s[i+k:i+2*k], updating dp[i] = max(dp[i], 1 + dp[i+k]). This captures all valid state transitions for optimal moves.

Use Rolling Hash for Efficient Prefix Comparison

Compute hash values for all prefixes using a rolling hash to compare s[i:i+k] and s[i+k:i+2*k] in constant time. This prevents repeated O(k) substring comparisons and speeds up the DP solution, essential for strings up to length 4000.

Finalize Result and Edge Cases

After filling dp, the answer is dp[0]. Handle edge cases such as a string of identical letters, where each character can be deleted individually, or strings with no repeating prefix, where the only deletion is the entire string at once.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) in the worst case without optimization, but rolling hash reduces substring comparisons to O(1), keeping the overall solution within acceptable bounds. Space complexity is O(n) for the dp array and hash arrays.

What Interviewers Usually Probe

Asks if dynamic programming is suitable for prefix-based deletions.
Mentions performance concerns for strings up to 4000 characters.
Checks understanding of rolling hash for substring comparison.

Common Pitfalls or Variants

Common pitfalls

Forgetting to compare only valid k-length prefixes within bounds.
Ignoring edge cases where the string has repeated single characters.
Recomputing substrings without hashing, causing timeouts.

Follow-up variants

Maximum deletions on a string allowing overlapping prefix matches.
Find maximum deletions where substrings may be reversed before comparison.
Calculate maximum deletions with additional constraint on minimum prefix length.

FAQ

What is the key pattern in Maximum Deletions on a String?

The problem follows a state transition dynamic programming pattern, comparing prefixes to determine valid deletions.

How does rolling hash improve performance?

Rolling hash allows constant-time substring comparison, avoiding repeated O(k) string operations in the DP approach.

Can single-character strings be deleted one by one?

Yes, each character can be deleted individually if no larger prefix matches exist, maximizing operation count.

What is the role of the dp array?

dp[i] stores the maximum deletions possible from position i to the end, guiding optimal state transitions.

How do I handle overlapping prefixes?

Only delete the first k characters if the next k characters match exactly, ensuring no misaligned overlaps affect dp updates.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i)$, which represents the maximum number of operations needed to delete all characters from $s[i..]$. The answer is $dfs(0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def deleteString(self, s: str) -> int:
        @cache
        def dfs(i: int) -> int:
            if i == n:
                return 0
            ans = 1
            for j in range(1, (n - i) // 2 + 1):
                if s[i : i + j] == s[i + j : i + j + j]:
                    ans = max(ans, 1 + dfs(i + j))
            return ans

        n = len(s)
        return dfs(0)

Solution 2: Dynamic Programming

We can change the memoization search in Solution 1 to dynamic programming. Define $f[i]$ to represent the maximum number of operations needed to delete all characters from $s[i..]$. Initially, $f[i]=1$, and the answer is $f[0]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def deleteString(self, s: str) -> int:
        @cache
        def dfs(i: int) -> int:
            if i == n:
                return 0
            ans = 1
            for j in range(1, (n - i) // 2 + 1):
                if s[i : i + j] == s[i + j : i + j + j]:
                    ans = max(ans, 1 + dfs(i + j))
            return ans

        n = len(s)
        return dfs(0)

Continue Practicing

#3291 minimum number of valid strings to form target i #3292 minimum number of valid strings to form target ii #2223 sum of scores of built strings