2430. Maximum Deletions on a String

HardStringDynamic ProgrammingString MatchingHash FunctionRolling Hash

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 first i letters are exactly the same as the next i letters. This can be done for any i satisfying 1 <= 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 to n, the length of the string), there are no operations left to perform, hence the base case of the recursion is dfs(i) = 0.
For any position i in the string, we try to find any index i + j such that s[i : i + j] is equal to s[i + j : i + 2 * j], which means we can perform an operation to delete s[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 index i + 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

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 index i. This helps us in breaking down the larger problem into smaller ones.
The base case of our recursion occurs when i reaches n, the length of s, meaning that there is no more string left to delete. In this case, dfs(i) returns 0 because no operations can be performed.
For any given index i, we iterate through all possible values of j such that 1 <= 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 to s[i + j : i + 2 * j]. If they are equal, we can delete s[i : i + j]. We then call dfs(i + j) to find out how many more operations can be performed starting from index i + j.
We use the max function to keep track of the maximum number of operations that we can perform. The variable ans is updated with 1 + 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's functools module for memoization. This stores the result of dfs(i) the first time it is computed for any index i, and subsequent calls with the same i 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Example 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 index i.
We call dfs(0) because we want to start from the beginning of the string.
At index 0, we have the whole string s = "aabbcc" to work with. We look for j's where 1 <= j <= (n - i) / 2 which translates to 1 <= j <= 3 for our string.
For j = 1, we check if s[0 : 1] ("a") is the same as s[1 : 2] ("a"). They match, so we can perform a delete operation. We also call dfs(1) to find the maximum number of operations from s = "abbcc".
Now, inside dfs(1), we repeat the process. We find that there are no j values that allow us to perform a delete operation, so dfs(1) returns 0.
Since dfs(1) returns 0, the maximum operations for j = 1 at i = 0 is 1 + dfs(1) which equals 1.
Next, we try j = 2. We find that s[0 : 2] ("aa") is the same as s[2 : 4] ("bb"), which do not match, so we cannot perform a delete operation for this j.
Finally, we try j = 3, and find that s[0 : 3] ("aab") is not equal to s[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 from dfs(0) is 1, which we've previously calculated.
No more operations can be performed, so the max number of operations for the entire string is 1.
Using memoization with the @cache decorator, if dfs(1) was called again, it would immediately return 0 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

Not Sure What to Study? Take the 2-min Quiz：

Which of the following problems can be solved with backtracking (select multiple)

Generating subsetsGenerating random numbersGenerating permutationsSorting integers

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 is n. Thus, the recursion stack could potentially take up O(n) space.
Cache: Since the cache stores the results for each unique state (i), and there are n possible unique states, the space complexity for memoization is also O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Combinatorial problemsRandom number generationTopological sortingMatrix multiplication

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2430. Maximum Deletions on a String

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings