LeetCode Problem 2430

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming, Rolling Hash, String Matching, Hash Function

Solution

Maximum Deletions on a String

Problem Understanding

The problem gives us a string s consisting only of lowercase English letters. We want to completely delete the string using the maximum possible number of operations.

In a single operation, we have two possible actions:

1. Delete the entire remaining string immediately.
2. Delete only the first i characters, but only if:

• 1 <= i <= len(s) / 2
• the first i characters are exactly equal to the next i characters.

The second operation is the interesting one. It means we can only delete a prefix if the string starts with two identical consecutive blocks.

For example:

s = "ababxyz"

We can delete "ab" because:

first 2 chars  = "ab"
next 2 chars   = "ab"

After deletion, the string becomes:

"abxyz"

The goal is not to minimize operations. Instead, we want the maximum number of operations possible before the string becomes empty.

The constraints are important:

1 <= s.length <= 4000

A length of 4000 is too large for exponential recursion or repeated substring comparisons using naive slicing inside nested loops. We need an algorithm around O(n²).

Several edge cases are important:

• Strings with no repeated adjacent prefixes, such as "abcdef", can only be deleted in one operation.
• Strings with many repeated characters, such as "aaaaa", allow many small deletions.
• Overlapping repeated patterns can create multiple valid choices, so greedy decisions are not always optimal.
• Repeated substring comparisons can become expensive if implemented naively.

This problem is fundamentally a dynamic programming problem combined with efficient substring comparison.

Approaches

Brute Force Approach

A brute force solution tries every valid deletion recursively.

Suppose we are currently at string s[i:]. We test every possible length k such that:

s[i:i+k] == s[i+k:i+2k]

If the condition holds, we recursively solve the remaining suffix:

solve(i + k)

We also always have the option to delete the entire remaining string in one operation.

The recurrence becomes:

dp[i] = 1 + max(dp[i+k]) for every valid k

The issue is substring comparison cost.

If we compare substrings directly:

s[i:i+k] == s[i+k:i+2*k]

each comparison costs O(k).

There are O(n²) possible (i, k) pairs, so the total complexity becomes:

O(n³)

With n = 4000, this is too slow.

Key Insight

The expensive part is repeatedly checking whether two substrings are equal.

Instead of comparing substrings character by character every time, we can preprocess information that allows us to answer substring equality queries efficiently.

A very effective technique here is computing the Longest Common Prefix, abbreviated LCP.

Define:

lcp[i][j]

as the length of the longest common prefix between:

s[i:]
and
s[j:]

For example:

s = "aaabaab"

lcp[0][1]

represents the common prefix length between:

"aaabaab"
"aabaab"

which is 2.

Once we know lcp[i][j], we can determine whether two substrings of length k are equal in constant time:

s[i:i+k] == s[j:j+k]
iff
lcp[i][j] >= k

This converts expensive substring comparisons into O(1) checks.

We can compute the entire LCP table in O(n²) using dynamic programming from right to left.

Then we run another DP to compute the maximum deletions.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n)	Recursively tries all deletions with expensive substring comparisons
Optimal DP + LCP	O(n²)	O(n²)	Uses precomputed longest common prefixes for constant-time comparisons

Algorithm Walkthrough

Step 1: Define the DP State

Let:

dp[i]

represent the maximum number of operations needed to delete the suffix:

s[i:]

Our final answer will be:

dp[0]

Step 2: Build the LCP Table

We create a 2D array:

lcp[n][n]

where:

lcp[i][j]

stores the length of the common prefix between:

s[i:]
and
s[j:]

We fill the table from bottom-right toward top-left.

If:

s[i] == s[j]

then:

lcp[i][j] = 1 + lcp[i+1][j+1]

Otherwise:

lcp[i][j] = 0

This works because matching prefixes extend one character further if the current characters are equal.

Step 3: Initialize the DP Array

Every suffix can always be deleted in one operation by removing the entire remaining string.

So initially:

dp[i] = 1

for all i.

Step 4: Try Every Valid Prefix Length

For each starting position i, try every possible prefix length k.

The prefix and following substring are:

s[i:i+k]
s[i+k:i+2k]

These substrings are equal if:

lcp[i][i+k] >= k

If true, we can delete the first block and continue from:

i + k

So:

dp[i] = max(dp[i], 1 + dp[i+k])

Step 5: Return the Answer

The result is:

dp[0]

since it represents the maximum operations needed for the entire string.

Why it works

The algorithm works because dp[i] explores every valid first deletion from suffix s[i:].

For every valid deletion length k, the remaining problem becomes exactly the same problem on suffix s[i+k:]. This optimal substructure makes dynamic programming applicable.

The LCP table guarantees correct substring equality checking. Since:

lcp[i][j]

stores the exact number of matching characters from both positions, the condition:

lcp[i][j] >= k

is equivalent to saying the next k characters are identical.

Therefore, the DP considers all legal operations and always chooses the sequence yielding the maximum number of deletions.

Python Solution

class Solution:
    def deleteString(self, s: str) -> int:
        n = len(s)

        # lcp[i][j] = longest common prefix length
        # between s[i:] and s[j:]
        lcp = [[0] * (n + 1) for _ in range(n + 1)]

        # Build LCP table from bottom-right
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if s[i] == s[j]:
                    lcp[i][j] = 1 + lcp[i + 1][j + 1]

        # dp[i] = maximum deletions for s[i:]
        dp = [1] * n

        # Process from right to left
        for i in range(n - 1, -1, -1):

            # Try every possible deletion length
            for length in range(1, (n - i) // 2 + 1):

                # Check whether:
                # s[i:i+length] == s[i+length:i+2*length]
                if lcp[i][i + length] >= length:
                    dp[i] = max(dp[i], 1 + dp[i + length])

        return dp[0]

The implementation begins by constructing the LCP table. The table is built from right to left because each state depends on lcp[i+1][j+1].

If two characters match, we extend the common prefix length by one. Otherwise, the common prefix is zero.

Next, we create the DP array. Each position starts with value 1 because deleting the whole remaining suffix is always possible.

For every index i, we try all valid prefix lengths. The maximum valid length is (n - i) // 2 because we need room for two equal consecutive blocks.

The condition:

lcp[i][i + length] >= length

checks whether the two adjacent substrings are equal.

If they are equal, we can perform one deletion and continue solving from i + length.

Finally, dp[0] contains the maximum operations for the full string.

Go Solution

func deleteString(s string) int {
	n := len(s)

	// lcp[i][j] = longest common prefix length
	// between s[i:] and s[j:]
	lcp := make([][]int, n+1)
	for i := range lcp {
		lcp[i] = make([]int, n+1)
	}

	// Build LCP table
	for i := n - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if s[i] == s[j] {
				lcp[i][j] = 1 + lcp[i+1][j+1]
			}
		}
	}

	// dp[i] = maximum deletions for s[i:]
	dp := make([]int, n)

	// Every suffix can always be deleted in one operation
	for i := range dp {
		dp[i] = 1
	}

	// Fill DP from right to left
	for i := n - 1; i >= 0; i-- {

		// Try every possible deletion length
		for length := 1; length <= (n-i)/2; length++ {

			// Check substring equality
			if lcp[i][i+length] >= length {
				if 1+dp[i+length] > dp[i] {
					dp[i] = 1 + dp[i+length]
				}
			}
		}
	}

	return dp[0]
}

The Go implementation follows the same logic as the Python version.

The primary difference is explicit allocation of 2D slices for the LCP table. Go strings are byte indexed, which works correctly here because the input contains only lowercase English letters.

No special handling for integer overflow is needed because all values are bounded by n <= 4000.

Worked Examples

Example 1

s = "abcabcdabc"

LCP Observations

At index 0:

"abc"

matches the next "abc" starting at index 3.

So:

lcp[0][3] >= 3

DP Computation

i	Suffix	Best Action	dp[i]
9	"c"	delete all	1
8	"bc"	delete all	1
7	"abc"	delete all	1
6	"dabc"	delete all	1
5	"cdabc"	delete all	1
4	"bcdabc"	delete all	1
3	"abcdabc"	delete all	1
0	"abcabcdabc"	delete "abc", continue at 3	2

Final answer:

2

Example 2

s = "aaabaab"

Step-by-Step

Initial string:

aaabaab

Delete first "a":

aabaab

Delete first "aab":

aab

Delete first "a":

ab

Delete all:

""

DP States

i	Suffix	dp[i]
6	"b"	1
5	"ab"	1
4	"aab"	2
3	"baab"	1
2	"abaab"	1
1	"aabaab"	3
0	"aaabaab"	4

Final answer:

4

Example 3

s = "aaaaa"

At every step, we can delete one "a" because the next character is also "a".

DP Table

i	Suffix	dp[i]
4	"a"	1
3	"aa"	2
2	"aaa"	3
1	"aaaa"	4
0	"aaaaa"	5

Final answer:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Building the LCP table takes O(n²), and the DP transitions also take O(n²)
Space	O(n²)	The LCP table stores n² values

The dominant cost comes from the LCP table and the nested DP loops.

The key optimization is converting substring comparison from O(k) to O(1) using the precomputed LCP values. Without this optimization, the algorithm would degrade to cubic complexity.

Test Cases

solution = Solution()

assert solution.deleteString("abcabcdabc") == 2  # provided example
assert solution.deleteString("aaabaab") == 4     # provided example
assert solution.deleteString("aaaaa") == 5       # repeated single character

assert solution.deleteString("a") == 1           # smallest input
assert solution.deleteString("ab") == 1          # no valid split
assert solution.deleteString("aa") == 2          # one repeated character pair

assert solution.deleteString("abab") == 2        # repeated block
assert solution.deleteString("abcabc") == 2      # repeated substring

assert solution.deleteString("abcdef") == 1      # no repeated adjacent prefixes
assert solution.deleteString("zzzzzz") == 6      # maximum repeated deletions

assert solution.deleteString("abaaba") == 2      # repeated pattern once
assert solution.deleteString("aaaaaaaa") == 8    # many sequential deletions

assert solution.deleteString("abcdabcdabcd") == 3  # repeated larger block
assert solution.deleteString("mississippi") == 1   # mostly non-repeating structure

Test	Why
"abcabcdabc"	Validates standard repeated-prefix deletion
"aaabaab"	Tests multiple recursive deletions
"aaaaa"	Tests maximum possible operation count
"a"	Smallest boundary input
"ab"	No repeated adjacent substrings
"aa"	Simplest valid repeated case
"abab"	Basic repeated block
"abcabc"	Multi-character repeated prefix
"abcdef"	Completely unique characters
"zzzzzz"	Highly repetitive string
"abaaba"	Repeated structure appearing once
"aaaaaaaa"	Stress test for repeated deletions
"abcdabcdabcd"	Larger repeated blocks
"mississippi"	Complex overlapping character patterns

Edge Cases

Single Character String

A string like:

"a"

cannot perform any partial deletion because there is no second block to compare against.

A buggy implementation might incorrectly attempt substring comparisons beyond bounds. Our implementation avoids this because the loop:

for length in range(1, (n - i) // 2 + 1)

never executes when fewer than two blocks are possible.

Completely Non-Repeating Strings

Consider:

"abcdef"

No adjacent equal substrings exist anywhere.

Some incorrect solutions accidentally allow non-adjacent matches or overlapping comparisons. Our implementation only checks:

s[i:i+length]
and
s[i+length:i+2*length]

which guarantees the blocks are consecutive.

The result correctly remains 1.

Highly Repetitive Strings

Strings such as:

"aaaaaaaa"

create many valid deletion choices.

A greedy strategy might delete large chunks immediately and miss the optimal answer. For example, deleting "aaaa" first gives fewer operations than deleting one "a" at a time.

The DP solution avoids this issue by evaluating every valid deletion length and selecting the maximum possible operations.