LeetCode 2430. Maximum Deletions on a String Solution in Java, C++, Python & More | Explanation + Code

Description

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.

Solutions

Solution 1: 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 ≥ n, then dfs(i) = 0, return directly.
• Otherwise, we enumerate the length of the string j, where 1 ≤ j ≤ (n-1)/2. If s[i..i+j] = s[i+j..i+j+j], we can delete s[i..i+j], then dfs(i)=max(dfs(i), dfs(i+j)+1). We need to enumerate all j to find the maximum value of dfs(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] ≥ 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²), and the space complexity is O(n²). Here, n is the length of the string s.

PythonJavaC++GoTypeScript

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)(code-box)

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]; } }(code-box)

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); } };(code-box)

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) }(code-box)

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); }(code-box)

Solution 2: 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 ≤ j ≤ (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²), and the space complexity is O(n). Here, n is the length of the string s.

PythonJavaC++GoTypeScript

class Solution: def deleteString(self, s: str) -> int: n = len(s) g = [[0] * (n + 1) for _ in range(n + 1)] for i in range(n - 1, -1, -1): for j in range(i + 1, n): if s[i] == s[j]: g[i][j] = g[i + 1][j + 1] + 1 f = [1] * n for i in range(n - 1, -1, -1): for j in range(1, (n - i) // 2 + 1): if g[i][i + j] >= j: f[i] = max(f[i], f[i + j] + 1) return f[0](code-box)

class Solution { public int deleteString(String s) { int n = s.length(); int[][] 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; } } } int[] f = new int[n]; for (int i = n - 1; i >= 0; --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], f[i + j] + 1); } } } return f[0]; } }(code-box)

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]; for (int i = n - 1; ~i; --i) { f[i] = 1; for (int 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]; } };(code-box)

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] }(code-box)

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]; }(code-box)