Maximum Deletions on a String — Problem & Solution
Maximum Deletions on a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Deletions on a String is a hard coding problem on strings, hash table and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Hash Table, Dynamic Programming, Rolling Hash, String Matching
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of lowercase letters. In one operation you can either:
- delete all of
s, or - delete the first
iletters ofs, for some1 <= i <= s.length / 2, provided they are equal to the nextiletters — that is,sstarts with some block written twice in a row.
Return the maximum number of operations needed to delete all of s.
Example 1
Input: s = "abcabcdabc"
Output: 2
Explanation: Delete "abc" (it is followed by "abc"), leaving "abcdabc"; then delete everything. No first step can be followed by more deletions.
Example 2
Input: s = "aaabaab"
Output: 4
Explanation: Delete "a" → "aabaab", delete "aab" → "aab", delete "a" → "ab", delete all.
Example 3
Input: s = "aaaaa"
Output: 5
Explanation: Delete one 'a' at a time.
Constraints
1 <= s.length <= 4000s consists only of lowercase English letters
Hints for Maximum Deletions on a String
Hint 1
After some operations the string left is always a suffix of
s. So letdp[i]be the most operations that delete the suffix starting ati.Hint 2
dp[i] = 1 + max(dp[i + len])over everylenwiths[i..i+len) == s[i+len..i+2len), or1if none — iterateifrom the end.Hint 3
Comparing substrings naively costs
O(n)each. Precomputelcp[i][j], the length of the longest common prefix of the suffixes atiandj(lcp[i][j] = lcp[i+1][j+1] + 1whens[i] == s[j]); the halves match whenlcp[i][i+len] >= len.
How to solve Maximum Deletions on a String
Every intermediate string is a suffix of s, so a DP over suffixes works; the only expensive part is checking whether a suffix starts with a doubled block, which a longest-common-prefix table answers in O(1).
Approach
- Process
ifromn - 1down to0, maintaining the LCP row fori:lcp[j] = s[i] == s[j] ? lcpNext[j + 1] + 1 : 0forj > i. - Set
dp[i] = 1(delete the whole suffix). - For every
lenwithi + 2·len <= n, iflcp[i + len] >= len, the firstlenletters repeat:dp[i] = max(dp[i], 1 + dp[i + len]). - Return
dp[0].
Why it works
An operation removes a prefix of the current string, so the string is always a suffix s[i..], and the best number of further operations depends only on i. The LCP of suffixes i and i + len is at least len exactly when the two blocks are equal, so the transition set is exact.
Complexity
- Time —
O(n^2) - Space —
O(n) with two LCP rows
Pitfalls
- A full
n × nLCP table of ints is 64 MB atn = 4000; two rolling rows suffice because rowineeds only rowi + 1. - Deleting the whole string is always allowed, so
dp[i] >= 1— it is also the right final step. - Greedily deleting the shortest repeated block is wrong: the
aaabaabexample needs a longer block in the middle.
Reference solution
Python
def deleteString(s: str) -> int:
n = len(s)
dp = [0] * (n + 1)
nxt = [0] * (n + 2)
for i in range(n - 1, -1, -1):
cur = [0] * (n + 2)
ci = s[i]
for j in range(i + 1, n):
if s[j] == ci:
cur[j] = nxt[j + 1] + 1
best = 1
for length in range(1, (n - i) // 2 + 1):
if cur[i + length] >= length and dp[i + length] + 1 > best:
best = dp[i + length] + 1
dp[i] = best
nxt = cur
return dp[0]Java
public static int deleteString(String s) {
int n = s.length();
int[] dp = new int[n + 1], nxt = new int[n + 2], cur = new int[n + 2];
for (int i = n - 1; i >= 0; i--) {
Arrays.fill(cur, 0);
char ci = s.charAt(i);
for (int j = i + 1; j < n; j++) if (s.charAt(j) == ci) cur[j] = nxt[j + 1] + 1;
int best = 1;
for (int len = 1; i + 2 * len <= n; len++) {
if (cur[i + len] >= len) best = Math.max(best, dp[i + len] + 1);
}
dp[i] = best;
int[] t = nxt; nxt = cur; cur = t;
}
return dp[0];
}C++
int deleteString(string s) {
int n = s.size();
vector<int> dp(n + 1, 0), nxt(n + 2, 0), cur(n + 2, 0);
for (int i = n - 1; i >= 0; i--) {
fill(cur.begin(), cur.end(), 0);
for (int j = i + 1; j < n; j++) if (s[j] == s[i]) cur[j] = nxt[j + 1] + 1;
int best = 1;
for (int len = 1; i + 2 * len <= n; len++) {
if (cur[i + len] >= len) best = max(best, dp[i + len] + 1);
}
dp[i] = best;
swap(nxt, cur);
}
return dp[0];
}JavaScript
var deleteString = function(s) {
var n = s.length, dp = new Array(n + 1).fill(0);
var nxt = new Array(n + 2).fill(0), cur = new Array(n + 2).fill(0);
for (var i = n - 1; i >= 0; i--) {
for (var j = 0; j <= n + 1; j++) cur[j] = 0;
for (var j = i + 1; j < n; j++) if (s[j] === s[i]) cur[j] = nxt[j + 1] + 1;
var best = 1;
for (var len = 1; i + 2 * len <= n; len++) {
if (cur[i + len] >= len && dp[i + len] + 1 > best) best = dp[i + len] + 1;
}
dp[i] = best;
var t = nxt; nxt = cur; cur = t;
}
return dp[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets