2430. Maximum Deletions on a String

Description

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.

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 <= 4000
s consists only of lowercase English letters.

Solutions

Solution 1: Memoization Search

Thinking

With \(n\le 4000\), an operation deletes a prefix that equals the next block of the same length. Search states collapse to the start \(i\) of the remaining suffix. From \(i\), try lengths \(j\) and compare slices \(s[i:i+j]\) and \(s[i+j:i+2j]\); a match moves to \(i+j\) with one extra deletion. Deleting everything at once is always legal, so the answer is at least \(1\).

Memoize \(dfs(i)\). Slice comparison is linear in \(j\), and the total time \(O(n^2)\) fits the limit.

We design a function \(dfs(i)\), which represents the maximum number of operations needed to delete all characters from \(s[i..]\). The answer is \(dfs(0)\).

The calculation process of the function \(dfs(i)\) is as follows:

If \(i \geq n\), then \(dfs(i) = 0\), return directly.
Otherwise, we enumerate the length of the string \(j\), where \(1 \leq j \leq (n-1)/2\). If \(s[i..i+j] = s[i+j..i+j+j]\), we can delete \(s[i..i+j]\), then \(dfs(i)=max(dfs(i), dfs(i+j)+1)\). We need to enumerate all \(j\) to find the maximum value of \(dfs(i)\).

Here we need to quickly determine whether \(s[i..i+j]\) is equal to \(s[i+j..i+j+j]\). We can preprocess all the longest common prefixes of string \(s\), that is, \(g[i][j]\) represents the length of the longest common prefix of \(s[i..]\) and \(s[j..]\). In this way, we can quickly determine whether \(s[i..i+j]\) is equal to \(s[i+j..i+j+j]\), that is, \(g[i][i+j] \geq j\).

To avoid repeated calculations, we can use memoization search and use an array \(f\) to record the value of the function \(dfs(i)\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n^2)\). Here, \(n\) is the length of the string \(s\).

Python3JavaC++GoTypeScript

class Solution:
    def deleteString(self, s: str) -> int:
        @cache
        def dfs(i: int) -> int:
            if i == n:
                return 0
            ans = 1
            for j in range(1, (n - i) // 2 + 1):
                if s[i : i + j] == s[i + j : i + j + j]:
                    ans = max(ans, 1 + dfs(i + j))
            return ans

        n = len(s)
        return dfs(0)

class Solution {
    private int n;
    private Integer[] f;
    private int[][] g;

    public int deleteString(String s) {
        n = s.length();
        f = new Integer[n];
        g = new int[n + 1][n + 1];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    g[i][j] = g[i + 1][j + 1] + 1;
                }
            }
        }
        return dfs(0);
    }

    private int dfs(int i) {
        if (i == n) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        f[i] = 1;
        for (int j = 1; j <= (n - i) / 2; ++j) {
            if (g[i][i + j] >= j) {
                f[i] = Math.max(f[i], 1 + dfs(i + j));
            }
        }
        return f[i];
    }
}

class Solution {
public:
    int deleteString(string s) {
        int n = s.size();
        int g[n + 1][n + 1];
        memset(g, 0, sizeof(g));
        for (int i = n - 1; ~i; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (s[i] == s[j]) {
                    g[i][j] = g[i + 1][j + 1] + 1;
                }
            }
        }
        int f[n];
        memset(f, 0, sizeof(f));
        function<int(int)> dfs = [&](int i) -> int {
            if (i == n) {
                return 0;
            }
            if (f[i]) {
                return f[i];
            }
            f[i] = 1;
            for (int j = 1; j <= (n - i) / 2; ++j) {
                if (g[i][i + j] >= j) {
                    f[i] = max(f[i], 1 + dfs(i + j));
                }
            }
            return f[i];
        };
        return dfs(0);
    }
};

func deleteString(s string) int {
    n := len(s)
    g := make([][]int, n+1)
    for i := range g {
        g[i] = make([]int, n+1)
    }
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {
                g[i][j] = g[i+1][j+1] + 1
            }
        }
    }
    f := make([]int, n)
    var dfs func(int) int
    dfs = func(i int) int {
        if i == n {
            return 0
        }
        if f[i] > 0 {
            return f[i]
        }
        f[i] = 1
        for j := 1; j <= (n-i)/2; j++ {
            if g[i][i+j] >= j {
                f[i] = max(f[i], dfs(i+j)+1)
            }
        }
        return f[i]
    }
    return dfs(0)
}

function deleteString(s: string): number {
    const n = s.length;
    const f: number[] = new Array(n).fill(0);
    const dfs = (i: number): number => {
        if (i == n) {
            return 0;
        }
        if (f[i] > 0) {
            return f[i];
        }
        f[i] = 1;
        for (let j = 1; j <= (n - i) >> 1; ++j) {
            if (s.slice(i, i + j) == s.slice(i + j, i + j + j)) {
                f[i] = Math.max(f[i], dfs(i + j) + 1);
            }
        }
        return f[i];
    };
    return dfs(0);
}

Solution 2: Dynamic Programming

Thinking

Method 1 compares slices repeatedly and pays recursion overhead. Precompute LCP \(g[i][j]\) so equality is \(g[i][i+j]\ge j\) in \(O(1)\). Fill \(f[i]\) from the back; besides the LCP table the DP is one-dimensional.

We can change the memoization search in Solution 1 to dynamic programming. Define \(f[i]\) to represent the maximum number of operations needed to delete all characters from \(s[i..]\). Initially, \(f[i]=1\), and the answer is \(f[0]\).

We can enumerate \(i\) from back to front. For each \(i\), we enumerate the length of the string \(j\), where \(1 \leq j \leq (n-1)/2\). If \(s[i..i+j] = s[i+j..i+j+j]\), we can delete \(s[i..i+j]\), then \(f[i]=max(f[i], f[i+j]+1)\). We need to enumerate all \(j\) to find the maximum value of \(f[i]\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string \(s\).

Python3JavaC++GoTypeScript

class Solution:
    def deleteString(self, s: str) -> int:
        n = len(s)
        g = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    g[i][j] = g[i + 1][j + 1] + 1

        f = [1] * n
        for i in range(n - 1, -1, -1):
            for j in range(1, (n - i) // 2 + 1):
                if g[i][i + j] >= j:
                    f[i] = max(f[i], f[i + j] + 1)
        return f[0]

class Solution {
    public int deleteString(String s) {
        int n = s.length();
        int[][] g = new int[n + 1][n + 1];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    g[i][j] = g[i + 1][j + 1] + 1;
                }
            }
        }
        int[] f = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            f[i] = 1;
            for (int j = 1; j <= (n - i) / 2; ++j) {
                if (g[i][i + j] >= j) {
                    f[i] = Math.max(f[i], f[i + j] + 1);
                }
            }
        }
        return f[0];
    }
}

class Solution {
public:
    int deleteString(string s) {
        int n = s.size();
        int g[n + 1][n + 1];
        memset(g, 0, sizeof(g));
        for (int i = n - 1; ~i; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (s[i] == s[j]) {
                    g[i][j] = g[i + 1][j + 1] + 1;
                }
            }
        }
        int f[n];
        for (int i = n - 1; ~i; --i) {
            f[i] = 1;
            for (int j = 1; j <= (n - i) / 2; ++j) {
                if (g[i][i + j] >= j) {
                    f[i] = max(f[i], f[i + j] + 1);
                }
            }
        }
        return f[0];
    }
};

func deleteString(s string) int {
    n := len(s)
    g := make([][]int, n+1)
    for i := range g {
        g[i] = make([]int, n+1)
    }
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {
                g[i][j] = g[i+1][j+1] + 1
            }
        }
    }
    f := make([]int, n)
    for i := n - 1; i >= 0; i-- {
        f[i] = 1
        for j := 1; j <= (n-i)/2; j++ {
            if g[i][i+j] >= j {
                f[i] = max(f[i], f[i+j]+1)
            }
        }
    }
    return f[0]
}

function deleteString(s: string): number {
    const n = s.length;
    const f: number[] = new Array(n).fill(1);
    for (let i = n - 1; i >= 0; --i) {
        for (let j = 1; j <= (n - i) >> 1; ++j) {
            if (s.slice(i, i + j) === s.slice(i + j, i + j + j)) {
                f[i] = Math.max(f[i], f[i + j] + 1);
            }
        }
    }
    return f[0];
}

2430. Maximum Deletions on a String

Description

Solutions

Solution 1: Memoization Search

Solution 2: Dynamic Programming

Comments