Maximum Deletions on a String

Hard
1631.

Maximum Deletions on a String

Maximum Deletions on a String is a hard coding problem on strings, hash table and dynamic programming, asked in Amazon and Google interviews.

You are given a string s of lowercase letters. In one operation you can either:

  • delete all of s, or
  • delete the first i letters of s, for some 1 <= i <= s.length / 2, provided they are equal to the next i letters — that is, s starts 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 <= 4000
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var deleteString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 i letters of s, for some 1 <= i <= s.length / 2, provided they are equal to the next i letters — that is, s starts 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 <= 4000
  • s consists only of lowercase English letters

Hints for Maximum Deletions on a String

  1. Hint 1

    After some operations the string left is always a suffix of s. So let dp[i] be the most operations that delete the suffix starting at i.

  2. Hint 2

    dp[i] = 1 + max(dp[i + len]) over every len with s[i..i+len) == s[i+len..i+2len), or 1 if none — iterate i from the end.

  3. Hint 3

    Comparing substrings naively costs O(n) each. Precompute lcp[i][j], the length of the longest common prefix of the suffixes at i and j (lcp[i][j] = lcp[i+1][j+1] + 1 when s[i] == s[j]); the halves match when lcp[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

  1. Process i from n - 1 down to 0, maintaining the LCP row for i: lcp[j] = s[i] == s[j] ? lcpNext[j + 1] + 1 : 0 for j > i.
  2. Set dp[i] = 1 (delete the whole suffix).
  3. For every len with i + 2·len <= n, if lcp[i + len] >= len, the first len letters repeat: dp[i] = max(dp[i], 1 + dp[i + len]).
  4. 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 × n LCP table of ints is 64 MB at n = 4000; two rolling rows suffice because row i needs only row i + 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 aaabaab example 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