2430. Maximum Deletions on a String
Problem Description
In this problem, you are given a string s
that consists only of lowercase English letters. Your task is to determine the maximum number of operations you can perform to delete the entire string. There are two types of operations you can perform:
- Delete the entire string at once.
- Delete the first
i
letters of the string if and only if the firsti
letters are exactly the same as the nexti
letters. This can be done for anyi
satisfying1 <= i <= s.length / 2
.
For example, let's assume you have the string s = "ababc"
. In one possible operation, you can delete the first two letters ("ab"
) because the first two letters ("ab"
) and the two following letters ("ab"
) are equal. This will leave you with the string "abc"
.
The goal is to return the maximum number of operations that can be applied to delete all of s
.
Intuition
To solve this problem, one approach is to use dynamic programming to break down the problem into smaller, more manageable subproblems. With dynamic programming, you can determine the optimal sequence of operations for each substring. The recursive function dfs(i)
is defined to determine the maximum operations that can be performed starting from the i
-th character of the string up to the end.
The key intuition for the solution is as follows:
- If we are at the end of the string (index
i
is equal ton
, the length of the string), there are no operations left to perform, hence the base case of the recursion isdfs(i) = 0
. - For any position
i
in the string, we try to find any indexi + j
such thats[i : i + j]
is equal tos[i + j : i + 2 * j]
, which means we can perform an operation to deletes[i : i + j]
. - For each valid
j
where a deletion can be performed, we recursively solve the problem for the remainder of the string starting from indexi + j
. - We use memoization (cache) to remember the results of subproblems we've already solved to avoid redundant calculations and improve efficiency.
- The final answer is the maximum number of operations we can perform, which is the best result out of all possible deletions from index
i
.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution makes use of dynamic programming and recursion to solve the problem. Dynamic programming is an optimization technique that solves problems by breaking them down into simpler subproblems and storing the results (usually in an array or hash table) to avoid redundant computations.
Here's how the implementation works:
-
We define a recursive function
dfs(i)
which computes the maximum number of operations that can be performed starting from indexi
. This helps us in breaking down the larger problem into smaller ones. -
The base case of our recursion occurs when
i
reachesn
, the length ofs
, meaning that there is no more string left to delete. In this case,dfs(i)
returns0
because no operations can be performed. -
For any given index
i
, we iterate through all possible values ofj
such that1 <= j <= (n - i) / 2
. These values represent potential cut points where we can split the string and perform a delete operation if the substring can be matched with the following string of the same length. -
During the iteration, we check if the substring
s[i : i + j]
is equal tos[i + j : i + 2 * j]
. If they are equal, we can deletes[i : i + j]
. We then calldfs(i + j)
to find out how many more operations can be performed starting from indexi + j
. -
We use the
max
function to keep track of the maximum number of operations that we can perform. The variableans
is updated with1 + dfs(i + j)
if a match is found since we have performed one operation plus however many more we can perform from the new starting point. -
To ensure the solution is efficient, we use the
@cache
decorator from Python'sfunctools
module for memoization. This stores the result ofdfs(i)
the first time it is computed for any indexi
, and subsequent calls with the samei
will use the cached result instead of recomputing it. -
At the end, the function
dfs(0)
is called to kick off the recursion from the beginning of the string, and the maximum number of operations for the entire string is returned.
By caching intermediate results, the implementation ensures that each subproblem is solved only once, leading to a significant performance improvement, particularly for larger strings. This is a common optimization in dynamic programming solutions to reduce the time complexity from exponential to polynomial.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the string s = "aabbcc"
to illustrate the solution approach.
- We start by defining the recursive function
dfs(i)
to find the maximum number of operations starting from indexi
. - We call
dfs(0)
because we want to start from the beginning of the string. - At index
0
, we have the whole strings = "aabbcc"
to work with. We look for j's where1 <= j <= (n - i) / 2
which translates to1 <= j <= 3
for our string. - For
j = 1
, we check ifs[0 : 1]
("a"
) is the same ass[1 : 2]
("a"
). They match, so we can perform a delete operation. We also calldfs(1)
to find the maximum number of operations froms = "abbcc"
. - Now, inside
dfs(1)
, we repeat the process. We find that there are noj
values that allow us to perform a delete operation, sodfs(1)
returns0
. - Since
dfs(1)
returns0
, the maximum operations forj = 1
ati = 0
is1 + dfs(1)
which equals1
. - Next, we try
j = 2
. We find thats[0 : 2]
("aa"
) is the same ass[2 : 4]
("bb"
), which do not match, so we cannot perform a delete operation for thisj
. - Finally, we try
j = 3
, and find thats[0 : 3]
("aab"
) is not equal tos[3 : 6]
("bcc"
) so we cannot perform a delete operation here as well. - Since only
j = 1
allowed us to perform an operation, the answer fromdfs(0)
is1
, which we've previously calculated. - No more operations can be performed, so the
max
number of operations for the entire string is1
. - Using memoization with the
@cache
decorator, ifdfs(1)
was called again, it would immediately return0
without recomputation.
This recursion and memoization process allows us to efficiently calculate the maximum number of operations that can be performed to delete the string s = "aabbcc"
, with the final answer being 1
.
Solution Implementation
1from functools import lru_cache
2
3class Solution:
4 def deleteString(self, string: str) -> int:
5 # Use lru_cache to memoize previously computed results
6 @lru_cache(None)
7 def dfs(index: int) -> int:
8 # If we've reached the end of the string, there's no more to delete, so return 0
9 if index == length:
10 return 0
11
12 # Initialize answer at 1, as there's at least the possibility of deleting the current character
13 answer = 1
14
15 # Try to find a duplicated substring starting at the current index
16 for j in range(1, (length - index) // 2 + 1):
17 # If a duplicate is found, recursively call dfs from the end of this duplicate substring
18 if string[index : index + j] == string[index + j : index + 2 * j]:
19 # Take the max of the current answer and 1 (for this deletion) + the result of dfs from the next index
20 answer = max(answer, 1 + dfs(index + j))
21
22 # Return the maximum number of deletions that can be made from this index
23 return answer
24
25 # Get the length of the string to avoid recalculating it
26 length = len(string)
27
28 # Begin the dfs from the start of the string
29 return dfs(0)
30
1class Solution {
2
3 public int deleteString(String s) {
4 // Length of the string
5 int n = s.length();
6 // g[i][j] will hold the length of the longest prefix of substring starting at i
7 // which is also a prefix of substring starting at j
8 int[][] longestPrefix = new int[n + 1][n + 1];
9
10 // Calculate the longest common prefix for all possible substrings
11 for (int i = n - 1; i >= 0; --i) {
12 for (int j = i + 1; j < n; ++j) {
13 if (s.charAt(i) == s.charAt(j)) {
14 longestPrefix[i][j] = longestPrefix[i + 1][j + 1] + 1;
15 }
16 }
17 }
18
19 // f[i] will hold the maximum number of ways to delete the substring starting at i
20 int[] maxDeleteWays = new int[n];
21
22 // Calculate the maximum number of ways to delete from each position
23 for (int i = n - 1; i >= 0; --i) {
24 // Initially, you can delete at least once
25 maxDeleteWays[i] = 1;
26 // Try to delete every possible substring length starting at i
27 for (int j = 1; j <= (n - i) / 2; ++j) {
28 // If the current substring can be deleted (found in its continuation)
29 if (longestPrefix[i][i + j] >= j) {
30 // Update f[i] if deleting substring leads to more delete operations
31 maxDeleteWays[i] = Math.max(maxDeleteWays[i], maxDeleteWays[i + j] + 1);
32 }
33 }
34 }
35
36 // Result is the maximum number of deletions starting from first character
37 return maxDeleteWays[0];
38 }
39}
40
1#include <vector>
2#include <string>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8 // Function to determine the maximum number of times we can delete a non-empty prefix from the string.
9 int deleteString(string s) {
10 int length = s.size();
11 // Define a matrix to store the longest common prefix information.
12 vector<vector<int>> longestCommonPrefix(length + 1, vector<int>(length + 1, 0));
13
14 // Calculate the longest common prefix for all the substrings.
15 for (int i = length - 1; i >= 0; --i) {
16 for (int j = i + 1; j < length; ++j) {
17 if (s[i] == s[j]) {
18 longestCommonPrefix[i][j] = longestCommonPrefix[i + 1][j + 1] + 1;
19 }
20 }
21 }
22
23 // A vector to store the maximum number of deletions starting from each index.
24 vector<int> maxDeletions(length, 1);
25
26 // Calculate the maximum number of deletions for every prefix.
27 for (int i = length - 1; i >= 0; --i) {
28 // Check all the possible next parts of the string to delete.
29 for (int j = 1; j <= (length - i) / 2; ++j) {
30 // Check if we have a matching prefix of at least length j.
31 if (longestCommonPrefix[i][i + j] >= j) {
32 // If so, update the maximum deletions at this index.
33 maxDeletions[i] = max(maxDeletions[i], maxDeletions[i + j] + 1);
34 }
35 }
36 }
37
38 // The maximum number of deletions starting from the beginning is the answer.
39 return maxDeletions[0];
40 }
41};
42
1function deleteString(s: string): number {
2 // Get the length of the input string.
3 const lengthOfString = s.length;
4 // Initialize an array to store the maximum number of identical contiguous substrings from each position.
5 const maxDeletes: number[] = new Array(lengthOfString).fill(1);
6
7 // Iterate over the string in reverse.
8 for (let i = lengthOfString - 1; i >= 0; --i) {
9 // Try to match substrings of all possible lengths starting from the current position.
10 for (let substringLength = 1; substringLength <= (lengthOfString - i) >> 1; ++substringLength) {
11 // Check if two contiguous substrings of half the remaining string are identical.
12 if (s.slice(i, i + substringLength) === s.slice(i + substringLength, i + 2 * substringLength)) {
13 // If they are, update the maximum number of deletes for the current position.
14 maxDeletes[i] = Math.max(maxDeletes[i], maxDeletes[i + substringLength] + 1);
15 }
16 }
17 }
18
19 // Return the maximum number of identical contiguous substrings that can be deleted from the entire string.
20 return maxDeletes[0];
21}
22
Time and Space Complexity
Time Complexity
The provided code uses a recursive function dfs
that explores the possibilities of splitting the string into two equal parts and checking if they are the same, then recursively applying the same logic to the rest of the string.
Considering that n
is the length of the string s
, the recursion could run theoretically for each starting position i
and try to match substrings of length j
, which can range from 1
to (n - i) / 2
. Therefore, in the worst-case scenario where the function checks all possibilities, it would make O(n/2)
comparisons for each i
. And since this is done for each i
, the overall time for comparisons is O(n^2/2)
.
Moreover, due to the use of memoization (indicated by @cache
), each state dfs(i)
is only computed once, which reduces the number of recursive computations from what would be exponential in the recursive case to linear in the number of unique states. Given that the states correspond to the starting indices of the string s
, there are n
unique states.
Hence, the memoization does not change the number of comparisons per se, but it does ensure that each state calculation is only done once, rather than being recomputed multiple times.
Thus, the time complexity, which involves the nested iteration and memoization, is O(n^3/2)
because for each i
, you could perform O(n/2)
comparisons and this is done for n
different starting positions. Hence, the final time complexity is O(n^3)
.
Space Complexity
The space complexity of the code is influenced by the maximum size of the recursion stack and the space used by the cache to store results of previous computations.
-
Recursion Stack: In the worst-case scenario, the recursion can go as deep as the length of the string
s
, which isn
. Thus, the recursion stack could potentially take upO(n)
space. -
Cache: Since the cache stores the results for each unique state (
i
), and there aren
possible unique states, the space complexity for memoization is alsoO(n)
.
Therefore, the total space complexity is the sum of the recursion stack and the cache, which gives us O(n) + O(n)
. However, since we drop constants in Big O notation, the space complexity simplifies to O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!