从现有字符串中移除字符创建回文字符串

Question

如何确定可以通过去除零个或多个字母从单词中得到的最长回文串的长度。

例如：amanQQQapl12345anacaZZZnalpaXXXna67890ma
最长回文串将有21个数字。

- Nitin Kabra

---

我还没有尝试过任何东西..需要一些逻辑上的帮助.. - Nitin Kabra

请标记为算法。这样你会更快地得到答案。 - Hindol

可能是重复的问题：如何找到最长回文子序列？ - Li-aung Yip

请注意，如果您在谷歌上搜索，您会找到最长回文子序列和最长回文子串的算法。您的问题是子序列版本。 - Li-aung Yip

Answer 1

这可以通过动态规划来解决。将 d[i, j] 定义为原始字符串中最长回文的长度。

如果 s[i] = s[j]，则 d[i, j] = max(d[i+1, j-1] + 2, d[i, j-1], d[i+1, j])。

否则，d[i, j] = max(d[i, j-1], d[i+1, j])。

- Rambo

---

请正确格式化并解释一下它的工作原理，谢谢。 - Li-aung Yip

Answer 2

W中最长的回文是W及其镜像的最长公共子序列。

你可以在O(n²)时间和O(n)空间内计算它，其中n是W的长度，但如果你知道只需要删除一些字符就能使一个回文变得更好，你可以获得更好的复杂度。

- Thomash

---

这似乎不是真的。请考虑“abcdecba”。 - Jirka Hanika

'abcdecba'和'abcedcba'的最长公共子序列是'abcdcba'（或长度相同的'abcecba'）。我看不出你的问题在哪里。 - Thomash

Answer 3

回文可以最多有一个奇数计数的字母，即中间的字母，以及任意数量的偶数计数的字母。

您可以计算每个字母的频率。如果对于每个字母来说不是全有或全无的情况，则为每个字母添加计数/2*2，并在任何字母具有奇数计数时添加一。

- Peter Lawrey

Answer 4

这是对@Rambo答案的适当实现，以防其他人发现他的回答过于简洁。我添加了先前结果的缓存，但条件是最多有1000个不同符号。由于多个分支使用相同的子分支，因此这提供了显着的加速。

int d[1000][1000] = {0}; // To store result of previous computation

int computeMaxPalindromeLength(vector<int>& a, int start, int end) {
    if(d[start][end] != 0) // If not precomputed, recompute.
        return d[start][end];
    if(start == end) { // The mid character should be taken as 
        d[start][end] = 1;
        return 1;
    }
    else if(start == end-1) {
        d[start][end] = (a[start] == a[end])?2:1;
        return d[start][end];
    }
    if(a[start] == a[end]) {
        d[start][end] = max( 2 + computeMaxPalindromeLength(a, start+1, end-1), 
            max(computeMaxPalindromeLength(a, start+1, end), computeMaxPalindromeLength(a, start, end-1)));
    } else {
        d[start][end] = max(computeMaxPalindromeLength(a, start+1, end), computeMaxPalindromeLength(a, start, end-1));
    }
    return d[start][end];
}

调用上述方法的方式如下：

vector<int>& a; // Convert each character of string to digit if working with alphanumeric characters.
int maxPalindromeLength = computeMaxPalindromeLength(a, 0, a.size()-1);

- saurabheights