Leetcode 2430: Maximum Deletions on a String

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.

Problem Analysis:

First, we could use depth search first algorithm to solve it. Suppose 1 ≤ s.length ≤ n, as if we find string partition [0, i-1] and [i, 2i-1] is same, then we can iterate searching partition [i, n], and we have 1 deletion operation. After iterating all possible deletion operations, we can get the answer.

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ h2;  
    }
};
class Solution {
public:
    int deleteString(string s) {
        find(s, 0, 0);
        
        return res_;
    }
                                                                   
    void find(const string& s, int index, int current) {
        if (index >= s.size()) return;
        
        res_ = max(res_, current + 1);
        int len{1};
        while (index + len + len <= s.size()) {
            auto it = data_.find({index, len});
            if (it != data_.end()) {
                if (it->second == -1) res_ = max(res_, current);
                else find(s, index + len, current + it->second);
                return;
            }
            
            bool flag{true};
            for (int i = 0; i < len; ++i) {
                if (s[index + i] != s[index + i + len]) {
                    flag = false;
                    break;
                }
            }
            if (!flag) {
                data_[{index, len}] = -1;
                res_ = max(res_, current);
            } else {
                data_[{index, len}] = 1;
                find(s, index + len, current + 1);
            }
            ++len;
        }
    }
private:
    int res_{0}; 
    unordered_map<pair<int, int>, bool, pair_hash> data_;
};

But the time complexity is O(n^n). We have to find better solution. Assume partitions [i, i + t] and [j, j + t] have the longest common substring, and its length is t, then if i + t ≥ j, then we can have a deletion operation from i to min(i + t, j). So we can use dynamic programming to iterate all deletions and find the answer.

Solution

class Solution {
public:
    int deleteString(string s) {
        vector<vector<int>> lcs(s.size() + 1, vector<int>(s.size() + 1, 0));
        vector<int> dp(s.size() + 1, 1);
        for (int i = s.size() - 1; i >= 0; --i) {
            for (int j = i + 1; j < s.size(); ++j) {
                if (s[i] == s[j])
                    lcs[i][j] = lcs[i + 1][j + 1] + 1;
                if (lcs[i][j] >= j - i)
                    dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        return dp[0];
    }
};

time complexity is O(s.size()²)

Space complexity is O(s.size()²)