Maximum Deletions on a String solution and explanation
5 more videos on this problem
Weekly Contest 313 | 6195. Maximum Deletions on a StringcodingMohan · 18:35 · 2K views
Maximum Deletions on a String (Leetcode Weekly 313)Soumya Bhattacharjee · 9:12 · 1K views
2430. Maximum Deletions on a String (Leetcode Hard)Programming Live with Larry · 50:24 · 1K views
Leetcode Weekly contest 313 - Hard - Maximum Deletions on a StringPrakhar Agrawal · 20:02 · 932 views
【每日一题】LeetCode 2430. Maximum Deletions on a StringHuifeng Guan · 24:45 · 732 views
LeetCode Hard 2430 Maximum Deletions on a Stringrobzingcod · 23:45 · 69 views
The 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
iletters ofsif the firstiletters ofsare equal to the followingiletters ins, for anyiin the range1 <= 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 <= 4000sconsists only of lowercase English letters.
Approach overview
Problem Overview: You are given a string s. In one operation, you may delete the first k characters if the prefix s[0:k] is equal to the next substring s[k:2k]. The goal is to maximize how many deletion operations you can perform until the string becomes empty or no more valid deletions exist.
Approach 1: Greedy Recursive with Memoization (O(n^3) time, O(n) space)
This approach explores every valid deletion length from the current index. For a position i, iterate len from 1 up to half the remaining string and check whether s[i:i+len] equals s[i+len:i+2*len]. If they match, recursively compute the best answer starting from i + len. Memoization caches results for each starting index to avoid recomputing the same suffix multiple times. String comparison inside the loop costs O(n), making the overall complexity roughly O(n^3) in the worst case.
Approach 2: Dynamic Programming with Rolling Hash (O(n^2) time, O(n) space)
This is the practical optimal approach. Use a DP array dp[i] representing the maximum deletions possible starting from index i. For each index, try all prefix lengths len where i + 2*len ≤ n. Instead of comparing substrings directly, compute hashes using a rolling hash. Two substring hashes can be compared in O(1), which avoids repeated O(n) comparisons. When two segments match, update dp[i] = max(dp[i], 1 + dp[i + len]). Iterate from right to left so that future states are already computed. This combines dynamic programming with efficient string matching and runs in O(n^2) time.
Approach 3: Dynamic Programming with LCP Table (O(n^2) time, O(n^2) space)
Another common technique precomputes an LCP (Longest Common Prefix) table where lcp[i][j] stores the length of the longest common prefix between suffixes starting at i and j. If lcp[i][i+len] ≥ len, the two substrings match and a deletion is valid. This converts substring equality checks into constant-time lookups. The DP transition is identical to the rolling-hash method, but the LCP table requires O(n^2) memory.
Recommended for interviews: Interviewers typically expect the dynamic programming solution combined with rolling hash or LCP preprocessing. Starting with the recursive idea shows you understand the deletion rule. Converting substring comparisons to constant-time checks demonstrates strong knowledge of string algorithms and reduces the complexity from cubic to quadratic.
Approach 1: Dynamic Programming Approach
This problem can be efficiently solved using dynamic programming. The idea is to use a DP array where dp[i] represents the maximum number of operations that can be performed to delete the substring s[i...n-1].
For each substring, check if its two halves match; if so, use these two halves as individual strings and continue the operation recursively. The dp array keeps track of the maximum operations available for every substring.
def max_deletions(s: str) -> int:
n = len(s)
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
for j in range(1, (n - i) // 2 + 1):
if s[i:i + j] == s[i + j:i + 2 * j]:
dp[i] = max(dp[i], 1 + dp[i + j])
else:
dp[i] = max(dp[i], 1)
return dp[0]public class MaxDeletions {
public int maxDeletions(String s) {
int n = s.length();
int[] dp = new int[n + 1];
for (int i = n - 1; i >= 0; i--) {
for (int j = 1; j <= (n - i) / 2; 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]);
} else {
dp[i] = Math.max(dp[i], 1);
}
}
}
return dp[0];
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int maxDeletions(string s) {
int n = s.size();
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
for (int j = 1; j <= (n - i) / 2; ++j) {
if (s.substr(i, j) == s.substr(i + j, j)) {
dp[i] = max(dp[i], 1 + dp[i + j]);
} else {
dp[i] = max(dp[i], 1);
}
}
}
return dp[0];
}function maxDeletions(s) {
let n = s.length;
let dp = new Array(n + 1).fill(0);
for (let i = n - 1; i >= 0; i--) {
for (let j = 1; j <= Math.floor((n - i) / 2); j++) {
if (s.substring(i, i + j) === s.substring(i + j, i + 2 * j)) {
dp[i] = Math.max(dp[i], 1 + dp[i + j]);
} else {
dp[i] = Math.max(dp[i], 1);
}
}
}
return dp[0];
}#include <string.h>
#include <stdio.h>
#include <stdlib.h>
int maxDeletions(char* s) {
int n = strlen(s);
int* dp = (int*)calloc(n + 1, sizeof(int));
for (int i = n - 1; i >= 0; --i) {
for (int j = 1; j <= (n - i) / 2; ++j) {
if (strncmp(s + i, s + i + j, j) == 0) {
dp[i] = (dp[i] > (1 + dp[i + j]) ? dp[i] : (1 + dp[i + j]));
} else {
dp[i] = (dp[i] > 1 ? dp[i] : 1);
}
}
}
int result = dp[0];
free(dp);
return result;
}public class Solution {
public int MaxDeletions(string s) {
int n = s.Length;
int[] dp = new int[n + 1];
for (int i = n - 1; i >= 0; i--) {
for (int j = 1; j <= (n - i) / 2; j++) {
if (s.Substring(i, j) == s.Substring(i + j, j)) {
dp[i] = Math.Max(dp[i], 1 + dp[i + j]);
}
else {
dp[i] = Math.Max(dp[i], 1);
}
}
}
return dp[0];
}
}The function max_deletions constructs a DP table from the end of the string to the beginning. For every position i, it tries to find the maximum number of deletions possible up to the end of the string. It checks all possible divisions into two strings of equal length (j).
Time Complexity: O(n^2), where n is the length of the string because for each starting point, we may check up to n possibilities of j.
Space Complexity: O(n), due to the DP array for storing the results of subproblems.
Approach 2: Greedy Recursive Approach
This problem can alternatively be solved using a greedy recursive strategy. Each step involves splitting the string and trying to delete as much as possible using the greedy approach based on discovered substrings that can be removed.
The recursive solution explores deleting the string by progressively recognizing matching segments, striving to delete the largest identical segment from the start and moving forward.
def max_deletions_recursive(s: str) -> int:
def solve(s):
if not s:
return 0
for i in range(1, len(s) // 2 + 1):
if s[:i] == s[i:2 * i]:
return 1 + solve(s[i:])
return 1
return solve(s)public class MaxDeletionsRecursive {
private int solve(String s) {
if (s.isEmpty()) return 0;
for (int i = 1; i <= s.length() / 2; i++) {
if (s.substring(0, i).equals(s.substring(i, 2 * i))) {
return 1 + solve(s.substring(i));
}
}
return 1;
}
public int maxDeletionsRecursive(String s) {
return solve(s);
}
}#include <iostream>
#include <string>
int solve(const std::string& s) {
if (s.empty()) return 0;
int n = s.size();
for (int i = 1; i <= n / 2; ++i) {
if (s.compare(0, i, s, i, i) == 0) {
return 1 + solve(s.substr(i));
}
}
return 1;
}
int maxDeletionsRecursive(std::string s) {
return solve(s);
}function maxDeletionsRecursive(s) {
function solve(s) {
if (s.length === 0) return 0;
for (let i = 1; i <= Math.floor(s.length / 2); i++) {
if (s.substring(0, i) === s.substring(i, i * 2)) {
return 1 + solve(s.substring(i));
}
}
return 1;
}
return solve(s);
}public class Solution {
private int Solve(string s) {
if (s.Length == 0) return 0;
for (int i = 1; i <= s.Length / 2; i++) {
if (s.Substring(0, i) == s.Substring(i, i)) {
return 1 + Solve(s.Substring(i));
}
}
return 1;
}
public int MaxDeletionsRecursive(string s) {
return Solve(s);
}
}The function max_deletions_recursive uses a helper function solve to recursively calculate maximum deletions. If a substring has matching consecutive segments, it removes the first and continues the recursion. If no such segments exist, it returns one (for full string deletion).
Time Complexity: Potentially O(n^2) due to substring creation, though recursive stack growth restrains efficiency.
Space Complexity: O(n^2) in worst-case due to recursive stack space and substring slicing.
Approach 3: Memoization Search
We design a function dfs(i), which represents the maximum number of operations needed to delete all characters from s[i..]. The answer is dfs(0).
The calculation process of the function dfs(i) is as follows:
- If
i geq n, thendfs(i) = 0, return directly. - Otherwise, we enumerate the length of the string
j, where1 leq j leq (n-1)/2. Ifs[i..i+j] = s[i+j..i+j+j], we can deletes[i..i+j], thendfs(i)=max(dfs(i), dfs(i+j)+1). We need to enumerate alljto find the maximum value ofdfs(i).
Here we need to quickly determine whether s[i..i+j] is equal to s[i+j..i+j+j]. We can preprocess all the longest common prefixes of string s, that is, g[i][j] represents the length of the longest common prefix of s[i..] and s[j..]. In this way, we can quickly determine whether s[i..i+j] is equal to s[i+j..i+j+j], that is, g[i][i+j] geq j.
To avoid repeated calculations, we can use memoization search and use an array f to record the value of the function dfs(i).
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the string s.
function deleteString(s: string): number {
const n = s.length;
const f: number[] = new Array(n).fill(0);
const dfs = (i: number): number => {
if (i == n) {
return 0;
}
if (f[i] > 0) {
return f[i];
}
f[i] = 1;
for (let j = 1; j <= (n - i) >> 1; ++j) {
if (s.slice(i, i + j) == s.slice(i + j, i + j + j)) {
f[i] = Math.max(f[i], dfs(i + j) + 1);
}
}
return f[i];
};
return dfs(0);
}func deleteString(s string) int {
n := len(s)
g := make([][]int, n+1)
for i := range g {
g[i] = make([]int, n+1)
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
g[i][j] = g[i+1][j+1] + 1
}
}
}
f := make([]int, n)
var dfs func(int) int
dfs = func(i int) int {
if i == n {
return 0
}
if f[i] > 0 {
return f[i]
}
f[i] = 1
for j := 1; j <= (n-i)/2; j++ {
if g[i][i+j] >= j {
f[i] = max(f[i], dfs(i+j)+1)
}
}
return f[i]
}
return dfs(0)
}Approach 4: Dynamic Programming
We can change the memoization search in Solution 1 to dynamic programming. Define f[i] to represent the maximum number of operations needed to delete all characters from s[i..]. Initially, f[i]=1, and the answer is f[0].
We can enumerate i from back to front. For each i, we enumerate the length of the string j, where 1 leq j leq (n-1)/2. If s[i..i+j] = s[i+j..i+j+j], we can delete s[i..i+j], then f[i]=max(f[i], f[i+j]+1). We need to enumerate all j to find the maximum value of f[i].
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the string s.
function deleteString(s: string): number {
const n = s.length;
const f: number[] = new Array(n).fill(1);
for (let i = n - 1; i >= 0; --i) {
for (let j = 1; j <= (n - i) >> 1; ++j) {
if (s.slice(i, i + j) === s.slice(i + j, i + j + j)) {
f[i] = Math.max(f[i], f[i + j] + 1);
}
}
}
return f[0];
}func deleteString(s string) int {
n := len(s)
g := make([][]int, n+1)
for i := range g {
g[i] = make([]int, n+1)
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
g[i][j] = g[i+1][j+1] + 1
}
}
}
f := make([]int, n)
for i := n - 1; i >= 0; i-- {
f[i] = 1
for j := 1; j <= (n-i)/2; j++ {
if g[i][i+j] >= j {
f[i] = max(f[i], f[i+j]+1)
}
}
}
return f[0]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2), where n is the length of the string because for each starting point, we may check up to n possibilities of j. Space Complexity: O(n), due to the DP array for storing the results of subproblems. |
| Greedy Recursive Approach | Time Complexity: Potentially O(n^2) due to substring creation, though recursive stack growth restrains efficiency. Space Complexity: O(n^2) in worst-case due to recursive stack space and substring slicing. |
| Memoization Search | – |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Recursive with Memoization | O(n^3) | O(n) | Good for understanding the deletion rule and exploring all choices before optimization |
| Dynamic Programming + Rolling Hash | O(n^2) | O(n) | Best practical solution; avoids expensive substring comparisons |
| Dynamic Programming + LCP Table | O(n^2) | O(n^2) | Useful when you want deterministic substring comparisons without hashing |
Frequently asked questions
Is Maximum Deletions on a String easy or hard?
Maximum Deletions on a String is classified as a Hard problem. The challenge comes from combining string matching with dynamic programming and optimizing substring comparisons to avoid cubic time complexity.
Maximum Deletions on a String Python/Java solution
Python, Java, C++, and JavaScript implementations typically follow the same DP logic. Each solution builds a dp array and uses either rolling hash or an LCP table to quickly check if two adjacent substrings are equal before applying the DP transition.
How to solve Maximum Deletions on a String in O(n^2)?
Precompute substring hashes using a rolling hash technique. Use a DP array where dp[i] stores the maximum deletions possible from index i. For each possible prefix length, compare two substrings via hash in O(1) and update the DP state accordingly, resulting in overall O(n^2) time.
What is the best approach for Maximum Deletions on a String?
The most efficient approach uses dynamic programming combined with rolling hash or LCP preprocessing. A DP array stores the maximum deletions starting at each index, while hashing or LCP allows constant-time substring comparison. This reduces the complexity to O(n^2) instead of repeatedly comparing substrings in O(n).
Is Maximum Deletions on a String asked at Google/Amazon/Meta?
Problems involving rolling hash, substring comparison, and dynamic programming frequently appear in interviews at companies like Google and Amazon. This specific problem represents the type of advanced string DP question used to test optimization and hashing knowledge.
What data structure is used in Maximum Deletions on a String?
The core structure is a dynamic programming array that stores the best result for each starting index. Efficient implementations also use rolling hash arrays or an LCP table to compare substrings in constant time.
What is the time complexity of Maximum Deletions on a String?
The optimized solution runs in O(n^2) time and O(n) space using dynamic programming with rolling hash. A simpler recursive solution with direct substring comparisons can degrade to O(n^3) time due to repeated string checks.