增加最少字符变成回文 

1
给定字符串s,可在其任意位置插入元素，问最少插入多少元素能使得字符串变成回文字符串。
eg: ababda -> 加入子串d于首个a之前，变成adbada，即字符串变成回文。

解法1. 动态规划

1
dp(i, j) 表示子串s[i..j]变成回文串最少的花费
dp(i, j) = 0 if i > j
         = dp(i+1, j-1) if s[i] = s[j]
         = min(dp(i+1, j), dp(i, j-1))+1

时间复杂度O(N*2)
解法2. 问题的转化：最长公共子序列

  1. 与逆序串的回文

思路:考虑找到最长的回文子序列，那么添加剩下的几个不是回文的字符即可。

解法：通过将字符串与其逆序后字符串求最长公共子序列即可得到最长回文子串

return len(s) - lcs(s, s[::-1])

  1. 动态规划。
    1
    dp(i, j) 表示子串s[0..i-1]与p[0..j-1]的最长公共子序列的长度
dp(i, j) = 0 if i = 0 or j = 0
         = dp(i-1, j-1) if s[i-1] == p[j-1]
         = max(dp(i-1, j), dp(i, j-1))

时间复杂度O(n^2),空间复杂度O(n^2)
采用状态压缩后，可将空间压缩为O(n)，相比第一种方法更优

  1. 转换成最长上升子序列
    当字符串中不出现重复元素时，可将其转换成最长上升子序列。

    采用哈希表记录字符串s中所有字符出现的位置

对于匹配串p，对于每一个字符，利用哈希表获取字符串p的位置，找到最长上升的idx

1
def lcs(s, p):
    position = {}
    for i, val in enumerate(s):
        position[val] = i
    dp = []
    for c in p:
        if c not in position:
            continue
        j = position[c]
        i = bisect_left(dp, j)
        if i == len(dp):
            dp.append(j)
        else:
            dp[i] = j
    return len(dp)

时间复杂度为O(nlgn),空间复杂度为O(n)

但对于本题的情况，字符串如果不出现相同字符是没有意义的(此时答案显然为字符串长度)。