Maximum Deletions on a String - Solution & Explanation
Problem Statement
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.
For example, if s = "ababc", then in one operation, you could delete the first two letters of s to get "abc", since the first two letters of s and the following two letters of s are both equal to "ab".
Return the maximum number of operations needed to delete all of s.
Example 1:
Input: s = "abcabcdabc"
Output: 2
Explanation:
- 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
Explanation:
- 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 Explanation: In each operation, we can delete the first letter of s.
Constraints:
1 <= s.length <= 4000sconsists only of lowercase English letters.
Approach Overview
Problem Overview: You are given a string s. In one operation, you may delete the first k characters if the prefix s[0:k] is equal to the next substring s[k:2k]. The goal is to maximize how many deletion operations you can perform until the string becomes empty or no more valid deletions exist.
Approach 1: Greedy Recursive with Memoization (O(n^3) time, O(n) space)
This approach explores every valid deletion length from the current index. For a position i, iterate len from 1 up to half the remaining string and check whether s[i:i+len] equals s[i+len:i+2*len]. If they match, recursively compute the best answer starting from i + len. Memoization caches results for each starting index to avoid recomputing the same suffix multiple times. String comparison inside the loop costs O(n), making the overall complexity roughly O(n^3) in the worst case.
Approach 2: Dynamic Programming with Rolling Hash (O(n^2) time, O(n) space)
This is the practical optimal approach. Use a DP array dp[i] representing the maximum deletions possible starting from index i. For each index, try all prefix lengths len where i + 2*len ≤ n. Instead of comparing substrings directly, compute hashes using a rolling hash. Two substring hashes can be compared in O(1), which avoids repeated O(n) comparisons. When two segments match, update dp[i] = max(dp[i], 1 + dp[i + len]). Iterate from right to left so that future states are already computed. This combines dynamic programming with efficient string matching and runs in O(n^2) time.
Approach 3: Dynamic Programming with LCP Table (O(n^2) time, O(n^2) space)
Another common technique precomputes an LCP (Longest Common Prefix) table where lcp[i][j] stores the length of the longest common prefix between suffixes starting at i and j. If lcp[i][i+len] ≥ len, the two substrings match and a deletion is valid. This converts substring equality checks into constant-time lookups. The DP transition is identical to the rolling-hash method, but the LCP table requires O(n^2) memory.
Recommended for interviews: Interviewers typically expect the dynamic programming solution combined with rolling hash or LCP preprocessing. Starting with the recursive idea shows you understand the deletion rule. Converting substring comparisons to constant-time checks demonstrates strong knowledge of string algorithms and reduces the complexity from cubic to quadratic.
Approach 1: Dynamic Programming Approach
This problem can be efficiently solved using dynamic programming. The idea is to use a DP array where dp[i] represents the maximum number of operations that can be performed to delete the substring s[i...n-1].
For each substring, check if its two halves match; if so, use these two halves as individual strings and continue the operation recursively. The dp array keeps track of the maximum operations available for every substring.
The function max_deletions constructs a DP table from the end of the string to the beginning. For every position i, it tries to find the maximum number of deletions possible up to the end of the string. It checks all possible divisions into two strings of equal length (j).
Complexity
Time Complexity: O(n^2), where n is the length of the string because for each starting point, we may check up to n possibilities of j.
Space Complexity: O(n), due to the DP array for storing the results of subproblems.
Approach 2: Greedy Recursive Approach
This problem can alternatively be solved using a greedy recursive strategy. Each step involves splitting the string and trying to delete as much as possible using the greedy approach based on discovered substrings that can be removed.
The recursive solution explores deleting the string by progressively recognizing matching segments, striving to delete the largest identical segment from the start and moving forward.
The function max_deletions_recursive uses a helper function solve to recursively calculate maximum deletions. If a substring has matching consecutive segments, it removes the first and continues the recursion. If no such segments exist, it returns one (for full string deletion).
Code
Python
C++
Java
JavaScript
C#
Complexity
Time Complexity: Potentially O(n^2) due to substring creation, though recursive stack growth restrains efficiency.
Space Complexity: O(n^2) in worst-case due to recursive stack space and substring slicing.
Approach 3: 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).
The calculation process of the function dfs(i) is as follows:
- If
i geq n, thendfs(i) = 0, return directly. - Otherwise, we enumerate the length of the string
j, where1 leq j leq (n-1)/2. Ifs[i..i+j] = s[i+j..i+j+j], we can deletes[i..i+j], thendfs(i)=max(dfs(i), dfs(i+j)+1). We need to enumerate alljto find the maximum value ofdfs(i).
Here we need to quickly determine whether s[i..i+j] is equal to s[i+j..i+j+j]. We can preprocess all the longest common prefixes of string s, that is, g[i][j] represents the length of the longest common prefix of s[i..] and s[j..]. In this way, we can quickly determine whether s[i..i+j] is equal to s[i+j..i+j+j], that is, g[i][i+j] geq j.
To avoid repeated calculations, we can use memoization search and use an array f to record the value of the function dfs(i).
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
Approach 4: 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].
We can enumerate i from back to front. For each i, we enumerate the length of the string j, where 1 leq j leq (n-1)/2. If s[i..i+j] = s[i+j..i+j+j], we can delete s[i..i+j], then f[i]=max(f[i], f[i+j]+1). We need to enumerate all j to find the maximum value of f[i].
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2), where n is the length of the string because for each starting point, we may check up to n possibilities of j. Space Complexity: O(n), due to the DP array for storing the results of subproblems. |
| Greedy Recursive Approach | Time Complexity: Potentially O(n^2) due to substring creation, though recursive stack growth restrains efficiency. Space Complexity: O(n^2) in worst-case due to recursive stack space and substring slicing. |
| Memoization Search | — |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Recursive with Memoization | O(n^3) | O(n) | Good for understanding the deletion rule and exploring all choices before optimization |
| Dynamic Programming + Rolling Hash | O(n^2) | O(n) | Best practical solution; avoids expensive substring comparisons |
| Dynamic Programming + LCP Table | O(n^2) | O(n^2) | Useful when you want deterministic substring comparisons without hashing |
Video Solution
Weekly Contest 313 | 6195. Maximum Deletions on a String • codingMohan • 2,839 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Maximum Deletions on a String easy or hard?
Maximum Deletions on a String Python/Java solution
How to solve Maximum Deletions on a String in O(n^2)?
What is the best approach for Maximum Deletions on a String?
Is Maximum Deletions on a String asked at Google/Amazon/Meta?
What data structure is used in Maximum Deletions on a String?
What is the time complexity of Maximum Deletions on a String?
Ready to solve this problem?
Practice Maximum Deletions on a String with our built-in code editor and test cases.
Practice on FleetCode