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 _themaximum number of operations needed to delete all of _s.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8

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

1
2
3

Input: s = "aaaaa"
Output: 5
Explanation: In each operation, we can delete the first letter of s.

Constraints

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

Solution

Method 1 – Dynamic Programming with Rolling Hash

Intuition

The key idea is to use dynamic programming to find the maximum number of deletions. For each substring, we check if the first i characters are equal to the next i characters, which allows us to delete the prefix. Rolling hash helps us compare substrings efficiently, and we use a table to store the longest common prefix (lcp[i][j]) between substrings starting at i and j.

Approach

  1. Use a DP array where dp[i] is the maximum number of operations to delete s[i:].
  2. For each position i, try all possible lengths j (1 to (n-i)//2) such that s[i:i+j] == s[i+j:i+2j].
  3. Use a longest common prefix table (lcp[i][j]) to compare substrings in O(1) time.
  4. Update dp[i] as max(dp[i], 1 + dp[i+j]) for all valid j.
  5. The answer is dp[0].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int deleteString(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        vector<vector<int>> lcp(n+1, vector<int>(n+1, 0));
        for (int i = n-1; i >= 0; --i) {
            for (int j = n-1; j >= 0; --j) {
                if (s[i] == s[j]) lcp[i][j] = lcp[i+1][j+1] + 1;
            }
        }
        for (int i = n-1; i >= 0; --i) {
            dp[i] = 1;
            for (int j = 1; i + 2*j <= n; ++j) {
                if (lcp[i][i+j] >= j) dp[i] = max(dp[i], 1 + dp[i+j]);
            }
        }
        return dp[0];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def deleteString(s string) int {
    n := len(s)
    lcp := make([][]int, n+1)
    for i := range lcp {
        lcp[i] = make([]int, n+1)
    }
    for i := n-1; i >= 0; i-- {
        for j := n-1; j >= 0; j-- {
            if s[i] == s[j] {
                lcp[i][j] = lcp[i+1][j+1] + 1
            }
        }
    }
    dp := make([]int, n+1)
    for i := n-1; i >= 0; i-- {
        dp[i] = 1
        for j := 1; i+2*j <= n; j++ {
            if lcp[i][i+j] >= j {
                if dp[i] < 1+dp[i+j] {
                    dp[i] = 1+dp[i+j]
                }
            }
        }
    }
    return dp[0]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int deleteString(String s) {
        int n = s.length();
        int[][] lcp = new int[n+1][n+1];
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    lcp[i][j] = lcp[i+1][j+1] + 1;
                }
            }
        }
        int[] dp = new int[n+1];
        for (int i = n-1; i >= 0; i--) {
            dp[i] = 1;
            for (int j = 1; i+2*j <= n; j++) {
                if (lcp[i][i+j] >= j) {
                    dp[i] = Math.max(dp[i], 1 + dp[i+j]);
                }
            }
        }
        return dp[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun deleteString(s: String): Int {
        val n = s.length
        val lcp = Array(n+1) { IntArray(n+1) }
        for (i in n-1 downTo 0) {
            for (j in n-1 downTo 0) {
                if (s[i] == s[j]) lcp[i][j] = lcp[i+1][j+1] + 1
            }
        }
        val dp = IntArray(n+1)
        for (i in n-1 downTo 0) {
            dp[i] = 1
            for (j in 1..((n-i)/2)) {
                if (lcp[i][i+j] >= j) dp[i] = maxOf(dp[i], 1 + dp[i+j])
            }
        }
        return dp[0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def deleteString(s: str) -> int:
    n = len(s)
    lcp = [[0]*(n+1) for _ in range(n+1)]
    for i in range(n-1, -1, -1):
        for j in range(n-1, -1, -1):
            if s[i] == s[j]:
                lcp[i][j] = lcp[i+1][j+1] + 1
    dp = [0]*(n+1)
    for i in range(n-1, -1, -1):
        dp[i] = 1
        for j in range(1, (n-i)//2+1):
            if lcp[i][i+j] >= j:
                dp[i] = max(dp[i], 1 + dp[i+j])
    return dp[0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn delete_string(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut lcp = vec![vec![0; n+1]; n+1];
        for i in (0..n).rev() {
            for j in (0..n).rev() {
                if s[i] == s[j] {
                    lcp[i][j] = lcp[i+1][j+1] + 1;
                }
            }
        }
        let mut dp = vec![0; n+1];
        for i in (0..n).rev() {
            dp[i] = 1;
            for j in 1..=((n-i)/2) {
                if lcp[i][i+j] >= j {
                    dp[i] = dp[i].max(1 + dp[i+j]);
                }
            }
        }
        dp[0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    deleteString(s: string): number {
        const n = s.length;
        const lcp: number[][] = Array.from({length: n+1}, () => Array(n+1).fill(0));
        for (let i = n-1; i >= 0; i--) {
            for (let j = n-1; j >= 0; j--) {
                if (s[i] === s[j]) lcp[i][j] = lcp[i+1][j+1] + 1;
            }
        }
        const dp: number[] = Array(n+1).fill(0);
        for (let i = n-1; i >= 0; i--) {
            dp[i] = 1;
            for (let j = 1; i+2*j <= n; j++) {
                if (lcp[i][i+j] >= j) dp[i] = Math.max(dp[i], 1 + dp[i+j]);
            }
        }
        return dp[0];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), because for each position we check all possible substring lengths and fill the lcp table.
  • 🧺 Space complexity: O(n^2), due to the lcp table and dp array.