Watch 6 video solutions for Maximum Deletions on a String, a hard level problem involving String, Dynamic Programming, Rolling Hash. This walkthrough by codingMohan has 2,778 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s consisting of only lowercase English letters. In one operation, you can:
s, ori letters of s if the first i letters of s are equal to the following i letters in s, for any i in the range 1 <= 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 <= 4000s consists only of lowercase English letters.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 | 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 |