2430. Maximum Deletions on a String LeetCode Solution
In this guide, you will get 2430. Maximum Deletions on a String LeetCode Solution with the best time and space complexity. The solution to Maximum Deletions on a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Deletions on a String
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.
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.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n^2)
2430. Maximum Deletions on a String LeetCode Solution in C++
class Solution {
public:
int deleteString(string s) {
const int n = s.length();
// lcs[i][j] := the number of the same letters of s[i..n) and s[j..n)
vector<vector<int>> lcs(n + 1, vector<int>(n + 1));
// dp[i] := the maximum number of operations needed to delete s[i..n)
vector<int> dp(n, 1);
for (int i = n - 1; i >= 0; --i)
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j])
lcs[i][j] = lcs[i + 1][j + 1] + 1;
if (lcs[i][j] >= j - i)
dp[i] = max(dp[i], dp[j] + 1);
}
return dp[0];
}
}; /* code provided by PROGIEZ */
2430. Maximum Deletions on a String LeetCode Solution in Java
class Solution {
public int deleteString(String s) {
final int n = s.length();
// lcs[i][j] := the number of the same letters of s[i..n) and s[j..n)
int[][] lcs = new int[n + 1][n + 1];
// dp[i] := the maximum number of operations needed to delete s[i..n)
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = n - 1; i >= 0; --i)
for (int j = i + 1; j < n; ++j) {
if (s.charAt(i) == s.charAt(j))
lcs[i][j] = lcs[i + 1][j + 1] + 1;
if (lcs[i][j] >= j - i)
dp[i] = Math.max(dp[i], dp[j] + 1);
}
return dp[0];
}
} // code provided by PROGIEZ
2430. Maximum Deletions on a String LeetCode Solution in Python
class Solution:
def deleteString(self, s: str) -> int:
n = len(s)
# lcs[i][j] := the number of the same letters of s[i..n) and s[j..n)
lcs = [[0] * (n + 1) for _ in range(n + 1)]
# dp[i] := the maximum number of operations needed to delete s[i..n)
dp = [1] * n
for i in reversed(range(n)):
for j in range(i + 1, n):
if s[i] == s[j]:
lcs[i][j] = lcs[i + 1][j + 1] + 1
if lcs[i][j] >= j - i:
dp[i] = max(dp[i], dp[j] + 1)
return dp[0] # code by PROGIEZ
