Scale Engineer

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 ProgrammingString MatchingRolling HashHash 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.

class Solution {    public int deleteString(String s) {        int n = s.length();        if (n == 0) {            return 0;        }        int[] dp = new int[n + 1];        // dp[i] = max operations for s.substring(i)        // dp[n] = 0 for empty string                for (int i = n - 1; i >= 0; i--) {            dp[i] = 1; // Operation to delete the entire remaining string            for (int j = 1; i + 2 * j <= n; j++) {                if (s.substring(i, i + j).equals(s.substring(i + j, i + 2 * j))) {                    dp[i] = Math.max(dp[i], 1 + dp[i + j]);                }            }        }        return dp[0];    }}

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

class Solution {private  int n;private  Integer[] f;private  int[][] g;public  int deleteString(String s) {    n = s.length();    f = new Integer[n];    g = new int[n + 1][n + 1];    for (int i = n - 1; i >= 0; --i) {      for (int j = i + 1; j < n; ++j) {        if (s.charAt(i) == s.charAt(j)) {          g[i][j] = g[i + 1][j + 1] + 1;        }      }    }    return dfs(0);  }private  int dfs(int i) {    if (i == n) {      return 0;    }    if (f[i] != null) {      return f[i];    }    f[i] = 1;    for (int j = 1; j <= (n - i) / 2; ++j) {      if (g[i][i + j] >= j) {        f[i] = Math.max(f[i], 1 + dfs(i + j));      }    }    return f[i];  }}

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 →

Next problem