# Maximum Deletions on a String
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-deletions-on-a-string)
Canonical: https://scaleengineer.com/dsa/problems/maximum-deletions-on-a-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** String
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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
## Brute Force Dynamic Programming
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.
**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.
**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.
### Explanation
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.

```java
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];
    }
}
```
### 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]`.

## Dynamic Programming with LCP Table Optimization
The brute-force DP approach is slow because of the repeated substring comparisons inside the nested loops. We can optimize this by pre-calculating the Longest Common Prefix (LCP) for all pairs of suffixes of the string. We can build an LCP table, `lcp[i][j]`, which stores the length of the longest common prefix between `s.substring(i)` and `s.substring(j)`. This table can be computed in `O(n^2)` time. With this table, checking if `s.substring(i, i+j)` equals `s.substring(i+j, i+2*j)` becomes an `O(1)` lookup: we just need to check if `lcp[i][i+j] >= j`. This optimization reduces the overall time complexity to `O(n^2)`.
**Time:** O(n^2). It takes `O(n^2)` to build the LCP table and `O(n^2)` for the main DP calculation. · **Space:** O(n^2). The LCP table requires `O(n^2)` space. The `dp` array takes `O(n)` space.
**Pros:** Significantly faster than the brute-force approach.; Fast enough to pass the given constraints.
**Cons:** High space complexity due to the O(n^2) LCP table, which might be an issue for memory-constrained environments, although it's feasible for n=4000.
### Explanation
The core DP logic remains the same: `dp[i]` is the max operations for `s.substring(i)`. The optimization comes from precomputation.

- First, we precompute an LCP table. Let `lcp[i][j]` be the length of the longest common prefix of suffixes starting at `i` and `j`.
- The `lcp` table is of size `(n+1) x (n+1)`. We can fill it using dynamic programming. We iterate `i` and `j` from `n-1` down to `0`.
- If `s.charAt(i) == s.charAt(j)`, then `lcp[i][j] = 1 + lcp[i+1][j+1]`. Otherwise, `lcp[i][j] = 0`. The base cases `lcp[i][n]` and `lcp[n][j]` are 0.
- After building the `lcp` table in `O(n^2)` time, we proceed with the main DP calculation.
- Iterate `i` from `n-1` down to `0`.
- Initialize `dp[i] = 1`.
- Iterate `j` from `1` to `(n-i)/2`.
- Instead of string comparison, check if `lcp[i][i+j] >= j`. This is an `O(1)` operation.
- If the condition is true, update `dp[i] = max(dp[i], 1 + dp[i+j])`.
- The final answer is `dp[0]`.

```java
class Solution {
    public int deleteString(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }

        // lcp[i][j]: length of longest common prefix of s.substring(i) and s.substring(j)
        int[][] lcp = new int[n + 1][n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    lcp[i][j] = 1 + lcp[i + 1][j + 1];
                }
            }
        }

        int[] dp = new int[n + 1]; // dp[n] = 0 by default
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = 1;
            for (int j = 1; i + 2 * j <= n; j++) {
                // Check if s.substring(i, i+j) == s.substring(i+j, i+2*j)
                if (lcp[i][i + j] >= j) {
                    dp[i] = Math.max(dp[i], 1 + dp[i + j]);
                }
            }
        }
        return dp[0];
    }
}
```
### Algorithm
- Let `n` be the length of `s`.
- Create an LCP table `lcp` of size `(n+1) x (n+1)`.
- Fill the `lcp` table:
  - Loop `i` from `n-1` down to `0`:
    - Loop `j` from `n-1` down to `0`:
      - If `s.charAt(i) == s.charAt(j)`:
        - `lcp[i][j] = 1 + lcp[i+1][j+1]`.
- 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 `lcp[i][i+j] >= j`:
      - `dp[i] = max(dp[i], 1 + dp[i+j])`.
- Return `dp[0]`.

## Space-Optimized Dynamic Programming with Z-Algorithm
This approach achieves the same `O(n^2)` time complexity as the LCP table method but improves the space complexity to `O(n)`. Instead of a large precomputed table, for each state `i`, we compute the necessary LCP information on-the-fly. The Z-algorithm is perfect for this. For each `i`, we compute the Z-array for the suffix `s[i:]`. The Z-value `z[j]` gives the LCP of `s[i:]` and `s[i+j:]`. The check `s[i:i+j] == s[i+j:i+2*j]` is equivalent to `z[j] >= j`. Computing the Z-array for `s[i:]` takes `O(n-i)` time. Summing over all `i` gives a total time of `O(n^2)`.
**Time:** O(n^2). For each `i` from `n-1` down to `0`, we run the Z-algorithm on a suffix of length `n-i`, which takes `O(n-i)` time. The total time is the sum `Σ O(n-i)` for `i` from `0` to `n-1`, which is `O(n^2)`. · **Space:** O(n). `O(n)` for the `dp` array and `O(n)` for the temporary Z-array used in each iteration of the outer loop.
**Pros:** Optimal time complexity for this problem.; Best space complexity, making it the most efficient overall solution.
**Cons:** More complex to implement due to the Z-algorithm.
### Explanation
The overall DP structure is the same. We optimize the check for `s.substring(i, i+j) == s.substring(i+j, i+2*j)`.

- We iterate `i` from `n-1` down to `0`. For each `i`, we need to find for which lengths `j` the prefix of `s.substring(i)` of length `j` is repeated.
- This is a classic use case for the Z-algorithm. The Z-array `Z` for a string `T` is defined such that `Z[k]` is the length of the longest common prefix between `T` and the suffix of `T` starting at `k`.
- For each `i`, we can run the Z-algorithm on the suffix `s.substring(i)`. Let the resulting Z-array be `z_i`. The condition `s.substring(i, i+j) == s.substring(i+j, i+2*j)` is then equivalent to `z_i[j] >= j`.
- The Z-algorithm for a string of length `m` runs in `O(m)` time. So for each `i`, we spend `O(n-i)` time to compute the Z-array. The total time for all `i` is `Σ(n-i)` which is `O(n^2)`.
- The space required is `O(n)` for the `dp` array and `O(n)` for the Z-array at each step, for a total of `O(n)` space.
- To implement this efficiently, we can convert the input string `s` to a character array once and pass an offset to the Z-algorithm function to avoid creating new substrings.

```java
class Solution {
    public int deleteString(String s) {
        int n = s.length();
        int[] dp = new int[n + 1]; // dp[n] = 0
        char[] sChars = s.toCharArray();
        
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = 1;
            int[] z = calculateZ(sChars, i);
            for (int j = 1; j <= (n - i) / 2; j++) {
                if (z[j] >= j) {
                    dp[i] = Math.max(dp[i], 1 + dp[i + j]);
                }
            }
        }
        return dp[0];
    }
    
    // Z-algorithm on a slice of a char array
    private int[] calculateZ(char[] t, int start) {
        int n = t.length - start;
        if (n == 0) return new int[0];
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && t[start + z[i]] == t[start + i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
}
```
### Algorithm
- Convert `s` to `char[] sChars`.
- Initialize `dp` array of size `n+1`. `dp[n] = 0`.
- Loop `i` from `n-1` down to `0`:
  - `dp[i] = 1`.
  - Compute Z-array for `sChars` starting from index `i`. Let it be `z`.
  - Loop `j` from `1` to `(n-i)/2`:
    - If `z[j] >= j`:
      - `dp[i] = max(dp[i], 1 + dp[i+j])`.
- Return `dp[0]`.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int deleteString(string s) {
    int n = s.size();
    int g[n + 1][n + 1];
    memset(g, 0, sizeof(g));
    for (int i = n - 1; ~i; --i) {
      for (int j = i + 1; j < n; ++j) {
        if (s[i] == s[j]) {
          g[i][j] = g[i + 1][j + 1] + 1;
        }
      }
    }
    int f[n];
    memset(f, 0, sizeof(f));
    function<int(int)> dfs = [&](int i) -> int {
      if (i == n) {
        return 0;
      }
      if (f[i]) {
        return f[i];
      }
      f[i] = 1;
      for (int j = 1; j <= (n - i) / 2; ++j) {
        if (g[i][i + j] >= j) {
          f[i] = max(f[i], 1 + dfs(i + j));
        }
      }
      return f[i];
    };
    return dfs(0);
  }
};

```

### Python

```python
class Solution:
    def deleteString(self, s: str) -> int: @ cache def dfs(i: int) -> int: if i == n: return 0 ans = 1 for j in range(1, (n - i) // 2 + 1): if s[i: i + j] == s[i + j: i + j + j]: ans = max(ans, 1 + dfs(i + j)) return ans n = len(s) return dfs(0)

```