Maximum Deletions on a String - Practice Coding Problems

Maximum Deletions on a String - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "ababc"

› Output: 2

💡 Note: First operation: delete "ab" (first 2 chars match next 2 chars), leaving "abc". Second operation: delete entire remaining string "abc". Total: 2 operations.

Example 2 — No Matching Prefix

$ Input: s = "abc"

› Output: 1

💡 Note: No matching prefix found ("a" ≠ "b"), so we can only delete the entire string in one operation.

Example 3 — Repeated Pattern

$ Input: s = "abab"

› Output: 2

💡 Note: First operation: delete "ab" (matches next "ab"), leaving "ab". Second operation: delete remaining "ab". Total: 2 operations.

Constraints

1 ≤ s.length ≤ 1000
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string s = "ababc"

Find Matching Prefix

First 2 chars "ab" match next 2 chars "ab"

Delete and Repeat

Delete prefix, continue with remaining string

Key Takeaway

🎯 Key Insight: Find matching prefixes to maximize deletion operations rather than deleting the entire string at once

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use dynamic programming to find the maximum number of deletion operations. At each position, we can either delete the entire remaining string or find a matching prefix to delete and recurse on the remaining substring. Best approach is bottom-up DP with Time: O(n³), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n³)	O(n)	Cache recursive results to avoid recalculation
Bottom-Up Dynamic Programming	O(n³)	O(n)	Build solution iteratively from the end of string
Recursive Brute Force	O(2^n)	O(n)	Try all possible prefix deletions recursively

Dynamic Programming with Memoization — Algorithm Steps

Use recursion with memoization
Cache results for each starting position
Return cached result if already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Calculate and cache result for position

Cache Hit

Return cached result for repeated subproblem

Optimized

Avoid redundant calculations

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int memo[1001];
int memo_set[1001];

int solve(char* s, int start, int len) {
    if (start >= len) {
        return 0;
    }
    
    if (memo_set[start]) {
        return memo[start];
    }
    
    // Option 1: Delete entire remaining string
    int maxOps = 1;
    
    // Option 2: Delete matching prefix
    int remainingLen = len - start;
    for (int i = 1; i <= remainingLen / 2; i++) {
        int match = 1;
        for (int j = 0; j < i; j++) {
            if (s[start + j] != s[start + i + j]) {
                match = 0;
                break;
            }
        }
        if (match) {
            int ops = 1 + solve(s, start + i, len);
            if (ops > maxOps) {
                maxOps = ops;
            }
        }
    }
    
    memo[start] = maxOps;
    memo_set[start] = 1;
    return maxOps;
}

int solution(char* s) {
    memset(memo_set, 0, sizeof(memo_set));
    return solve(s, 0, strlen(s));
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n) subproblems, each checking O(n) prefixes with O(n) string comparison

⚠ Quadratic Growth

Space Complexity

O(n)

Memoization table stores at most n entries plus recursion stack

⚡ Linearithmic Space

15.0K Views

Medium Frequency

~35 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler