Maximum Deletions on a String - Video Solutions
Weekly Contest 313 | 6195. Maximum Deletions on a String
Maximum Deletions on a String - Video Solution
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,839 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |