字符串的最大删除次数

问题陈述

这个问题给出的输入是一个字符串 s，它只包含小写英文字母。

删除字符串中所有字符，包括空格。

• 在这种情况下，如果 substr(s, 0, i) = substr(s, i, s.length - i) 或者 1 <= i <= s.length / 2，则 substr(s, 0, i) = substr(s, i, s.length - i)。
• 更具体地说，如果 s = "ababc"，则有可能通过减去 s 的前两个字母得到 "abc"，因为 s 的第一个和第二个字母以及 s 随后的两个字符都是 "ab"。

返回删除所有 s 所需的最大操作次数。

使用动态规划的 Java 方法

输出

代码解释

• deleteString 方法初始化动态规划数组 dp 并使用输入字符串和起始索引调用辅助方法。
• 辅助方法递归地计算从给定索引开始的最大删除次数。它遍历字符串，检查回文子字符串。如果找到回文，则递归调用自身，传入下一个索引。基本情况是当索引到达字符串末尾时。
• 如果没有找到回文子字符串，则返回 1，表示从该索引开始无法删除。

时间复杂度

• 这使我们相信辅助方法的时间复杂度为 O(n^2)，其中 n 是输入字符串的长度。从列表中删除最小项是 O(n) 操作；因此，删除所有项是 O(n^2)，但辅助方法只访问一次。

空间复杂度

• 空间复杂度为 O(n)，其中 n 是给定字符串的长度。我们选择了一个二维矩阵 dp，其维度大小为 n，以便方便地保存动态规划的中间结果。此外，在最坏的情况下，栈理论上甚至可以增长到 O(n)，这会将整个空间复杂度增加到 O(n)。

使用 HashMap 的 Java 方法

输出

代码解释

• 此代码旨在找出可以从字符串中删除的最大字符数，使剩余字符串成为回文。它首先使用 HashMap 计算每个字符的频率。如果所有字符都相同，则返回任何字符的计数作为结果。
• 否则，它递归地尝试所有可能的前缀长度，将字符串拆分为潜在的回文前缀和剩余后缀。对于每个有效的前缀长度，它检查前缀是否是回文。如果是，它递归地为剩余后缀调用函数，并相应地更新最大删除次数。

时间复杂度

• deleteString 函数的运行时间为 O(N^2) 数量级，其中 N 是输入字符串的长度。
• Do 函数（最坏情况）的时间复杂度为 O(N^2)。该函数遍历所有前缀长度，导致了这种最坏情况。
• do_check(O(N)) 的时间与 N 的子字符串长度成比例。

空间复杂度

• 由于使用了 HashMap map1、记忆化数组 dp，以及 N 是输入长度，因此程序的时间复杂度为 O(N)。

使用队列的 Java 方法

输出

代码解释

此代码旨在找出从给定字符串中删除字符所需的最大操作次数，同时保持原始字符串中长度至少为 1 的每个子字符串都是回文的属性。

• Deq 类管理两个队列以表示字符串中两个不同位置的子字符串。它跟踪子字符串之间匹配字符的数量。
• 在 Solution 类中，它遍历所有可能的子字符串，并检查下一个子字符串是否可以通过删除字符而成为回文。它将此信息存储在二维数组 samenext 中。

然后，它利用动态规划计算删除字符所需的最大操作次数。

时间复杂度

• 构建相同下一个矩阵：O(n^2)，因为它遍历所有子字符串。
• 动态规划：O(n^2)，由于嵌套循环。

空间复杂度

• 相同下一个矩阵：O(n^2) 用于存储布尔值。
• Deq 类：O(n) 用于存储字符。
• 动态规划数组：O(n) 用于存储中间结果。