How to Solve Maximum Deletions on a String

Start by applying dynamic programming to track the maximum deletions for each substring. Use a dp array where dp[i] stores the maximum operations for s[i:]. Compare prefixes efficiently with a rolling hash to detect repeated segments. By iterating through all valid prefix lengths and updating dp values, you can determine the highest number of deletions needed to completely remove the string.

Problem Statement

You are given a string s containing only lowercase English letters. In one operation, you may delete the first k characters if the substring of length k starting at the beginning equals the next k characters immediately following it.

Return the maximum number of operations required to delete all characters of s. For instance, if s = "ababc", you can delete "ab" first because it matches the next "ab", resulting in "abc", and continue until the string is empty.

Examples

Example 1

Input: s = "abcabcdabc"

Output: 2

• 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

• 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

In each operation, we can delete the first letter of s.

Constraints

• 1 <= s.length <= 4000
• s consists only of lowercase English letters.

Solution Approach

Dynamic Programming with Prefix Matching

Create a dp array where dp[i] represents the maximum deletions possible for s[i:]. Iterate from the end toward the start, and for each i, try all lengths of k where s[i:i+k] matches s[i+k:i+2*k], updating dp[i] = max(dp[i], 1 + dp[i+k]). This captures all valid state transitions for optimal moves.

Use Rolling Hash for Efficient Prefix Comparison

Compute hash values for all prefixes using a rolling hash to compare s[i:i+k] and s[i+k:i+2*k] in constant time. This prevents repeated O(k) substring comparisons and speeds up the DP solution, essential for strings up to length 4000.

Finalize Result and Edge Cases

After filling dp, the answer is dp[0]. Handle edge cases such as a string of identical letters, where each character can be deleted individually, or strings with no repeating prefix, where the only deletion is the entire string at once.

Complexity Analysis

Time complexity is O(n^2) in the worst case without optimization, but rolling hash reduces substring comparisons to O(1), keeping the overall solution within acceptable bounds. Space complexity is O(n) for the dp array and hash arrays.

What Interviewers Usually Probe

• Asks if dynamic programming is suitable for prefix-based deletions.
• Mentions performance concerns for strings up to 4000 characters.
• Checks understanding of rolling hash for substring comparison.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to compare only valid k-length prefixes within bounds.
• Ignoring edge cases where the string has repeated single characters.
• Recomputing substrings without hashing, causing timeouts.

Follow-up variants

• Maximum deletions on a string allowing overlapping prefix matches.
• Find maximum deletions where substrings may be reversed before comparison.
• Calculate maximum deletions with additional constraint on minimum prefix length.

How GhostInterview Helps

• Automatically tracks state transitions and computes dp array updates for all prefix lengths.
• Generates rolling hash comparisons to quickly detect repeated substrings.
• Highlights potential pitfalls and edge cases specific to Maximum Deletions on a String.

Topic Pages

• String
• Dynamic Programming
• Rolling Hash
• String Matching
• Hash Function

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the key pattern in Maximum Deletions on a String?

The problem follows a state transition dynamic programming pattern, comparing prefixes to determine valid deletions.

How does rolling hash improve performance?

Rolling hash allows constant-time substring comparison, avoiding repeated O(k) string operations in the DP approach.

Can single-character strings be deleted one by one?

Yes, each character can be deleted individually if no larger prefix matches exist, maximizing operation count.

What is the role of the dp array?

dp[i] stores the maximum deletions possible from position i to the end, guiding optimal state transitions.

How do I handle overlapping prefixes?

Only delete the first k characters if the next k characters match exactly, ensuring no misaligned overlaps affect dp updates.