You are given a string s consisting of only lowercase English letters. In one operation, you can:
s, ori 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 <= 4000s consists only of lowercase English letters.The key idea for Maximum Deletions on a String is to repeatedly delete prefixes when the prefix is equal to the substring that follows it. A brute-force comparison of substrings would be too slow, so an optimized strategy combines dynamic programming with efficient substring comparison.
Define a dp[i] state representing the maximum deletions possible starting from index i. For each position, try splitting the remaining string into two equal-length parts and check whether they match. If they match, you can delete the prefix and continue solving from the next index.
To compare substrings efficiently, techniques like rolling hash or longest common prefix (LCP) help reduce comparison time to near constant. This avoids repeated character-by-character checks and keeps the algorithm efficient.
Overall, the solution iterates over possible prefix lengths and uses memoization or bottom-up DP to compute the best result.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Rolling Hash | O(n^2) | O(n) |
| DP with Direct Substring Comparison (Naive) | O(n^3) | O(n) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
We can use dynamic programming to find the answer. Create a 0-indexed dp array where dp[i] represents the maximum number of moves needed to remove the first i + 1 letters from s.
What should we do if there is an i where it is impossible to remove the first i + 1 letters?
Use a sentinel value such as -1 to show that it is impossible.
How can we quickly determine if two substrings of s are equal? We can use hashing.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving string matching, dynamic programming, and hashing are common in FAANG-style interviews. While this exact question may not always appear, the techniques used in solving it—like rolling hash and DP optimization—are frequently tested.
Rolling hash allows efficient comparison of two substrings without checking every character. By precomputing hash values for prefixes, the algorithm can quickly verify whether two segments are identical, which is essential when trying many possible prefix splits.
Dynamic programming arrays are the primary structure used to store the best result starting at each index. To speed up substring comparison, rolling hash or prefix hash arrays are often used. These help compare substrings in constant or near-constant time.
The optimal approach uses dynamic programming combined with rolling hash or fast substring comparison. DP tracks the maximum deletions from each index, while hashing allows quick checks to see if two substrings are equal. This reduces the overall complexity to about O(n^2).