Maximum Deletions on a String

Hard

#2214Time: O(n^3), where n is the length of the string. The outer loop runs `n` times. The inner loop runs up to `n/2` times. Inside the inner loop, `substring` creation and `equals` comparison take `O(j)` time, where `j` can be up to `n/2`. This gives a complexity of `Σ(i=0 to n-1) Σ(j=1 to (n-i)/2) O(j)`, which is `O(n^3)`.Space: O(n) for the DP array. The substrings created in the loop also take space, but they can be considered temporary.1 company

Patterns

Dynamic Programming String Matching Rolling Hash Hash Function

Data structures

String

Companies

DE Shaw

Prompt

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 i 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 <= 4000
s consists only of lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. We define dp[i] as the maximum number of operations to delete the substring starting at index i. We compute dp[i] for i from n-1 down to 0. For each i, we consider all possible first moves. The base case is that we can always delete the entire remaining substring in one operation, so dp[i] is at least 1. Then, we check for all possible lengths j if the prefix of length j can be deleted. If s.substring(i, i+j) equals s.substring(i+j, i+2*j), we can perform an operation and transition to the state i+j. The number of operations would be 1 + dp[i+j]. We take the maximum over all such possibilities.

Algorithm

Let n be the length of s.
Initialize dp array of size n+1. dp[n] = 0.
Loop i from n-1 down to 0:
- dp[i] = 1.
- Loop j from 1 to (n-i)/2:
  - If s.substring(i, i+j).equals(s.substring(i+j, i+2*j)):
    - dp[i] = max(dp[i], 1 + dp[i+j]).
Return dp[0].

Walkthrough

The core idea is to build up a solution from smaller subproblems. A subproblem is defined by the starting index i of the string we need to delete, i.e., s.substring(i). Let dp[i] be the maximum number of operations for this subproblem.

We can compute the dp array from right to left:

Create a DP array dp of size n+1, where n is the length of the string s. dp[i] will store the maximum operations for the suffix s.substring(i). Initialize dp[n] = 0 (empty string needs 0 operations).
Iterate i from n-1 down to 0.
For each i, initialize dp[i] = 1, representing the single operation of deleting the entire remaining substring s.substring(i).
Then, iterate through all possible prefix lengths j from 1 to (n-i)/2.
In the inner loop, check if the prefix of length j is equal to the next j characters. This is done by comparing s.substring(i, i+j) with s.substring(i+j, i+2*j).
If they are equal, it means we can perform a prefix deletion operation. This move leads to the subproblem of deleting s.substring(i+j), which takes dp[i+j] operations. So, the total operations for this move would be 1 + dp[i+j].
Update dp[i] with the maximum value found: dp[i] = max(dp[i], 1 + dp[i+j]).
After the loops complete, dp[0] will hold the result for the entire string s.

The string comparison at each step takes O(j) time, leading to an overall cubic time complexity.

1class Solution {2    public int deleteString(String s) {3        int n = s.length();4        if (n == 0) {5            return 0;6        }7        int[] dp = new int[n + 1];8        // dp[i] = max operations for s.substring(i)9        // dp[n] = 0 for empty string10        11        for (int i = n - 1; i >= 0; i--) {12            dp[i] = 1; // Operation to delete the entire remaining string13            for (int j = 1; i + 2 * j <= n; j++) {14                if (s.substring(i, i + j).equals(s.substring(i + j, i + 2 * j))) {15                    dp[i] = Math.max(dp[i], 1 + dp[i + j]);16                }17            }18        }19        return dp[0];20    }21}

Complexity

Time

O(n^3), where n is the length of the string. The outer loop runs `n` times. The inner loop runs up to `n/2` times. Inside the inner loop, `substring` creation and `equals` comparison take `O(j)` time, where `j` can be up to `n/2`. This gives a complexity of `Σ(i=0 to n-1) Σ(j=1 to (n-i)/2) O(j)`, which is `O(n^3)`.

Space

O(n) for the DP array. The substrings created in the loop also take space, but they can be considered temporary.

Trade-offs

Pros

Simple to understand and implement.
Follows a standard dynamic programming pattern.

Cons

Too slow for the given constraints (n <= 4000), will result in Time Limit Exceeded.

Solutions

Solution

1class Solution {2private3  int n;4private5  Integer[] f;6private7  int[][] g;8public9  int deleteString(String s) {10    n = s.length();11    f = new Integer[n];12    g = new int[n + 1][n + 1];13    for (int i = n - 1; i >= 0; --i) {14      for (int j = i + 1; j < n; ++j) {15        if (s.charAt(i) == s.charAt(j)) {16          g[i][j] = g[i + 1][j + 1] + 1;17        }18      }19    }20    return dfs(0);21  }22private23  int dfs(int i) {24    if (i == n) {25      return 0;26    }27    if (f[i] != null) {28      return f[i];29    }30    f[i] = 1;31    for (int j = 1; j <= (n - i) / 2; ++j) {32      if (g[i][i + j] >= j) {33        f[i] = Math.max(f[i], 1 + dfs(i + j));34      }35    }36    return f[i];37  }38}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem