string - 求 K 的最大值，使得子序列 A 和 B 存在且满足上述条件

Question

给定一个字符串S长度n 。选择一个整数K和两个非空子序列 A和B长度K使其满足以下条件:

1. A = B即对于每个 i ith A 中的角色与 ith 相同B 中的角色。
2. 让我们表示用于构造 A 的索引如a1,a2,a3,...,an哪里ai belongs to S和B如b1,b2,b3,...,bn哪里bi belongs to S 。如果我们表示 A 中公共(public)索引的数量和B通过M然后M + 1 <= K 。

求 K 的最大值这样就可以找到子序列 A和B从而满足上述条件。

约束:
0 < N <= 10^5

我观察到的事情是:

• K = 0 的值如果给定字符串中的字符数全部不同，即 S = abcd 。
• K = length of S - 1如果字符串中的所有字符都相同，即 S = aaaa 。
• M 的值不能等于K因为那时M + 1 <= K不会是真的，即你不能有子序列 A和B满足A = B和a1 = b1, a2 = b2, a3 = b3, ..., an = bn .
• 如果字符串 S则 K = (Total number of times a character is repeated in the string if the repeatation count > 1) - 1 是回文。即S = tenet然后t重复 2次，e重复 2次，一个字符重复的总次数 = 4 , K = 4 - 1 = 3 .

我在设计解决上述问题的算法时遇到困难。

如果您需要更多说明，请在评论中告诉我。

Answer 1

(更新:参见O(n) answer。)

我们可以修改经典longest common subsequence递归以获取额外参数。

我希望 JavaScript 代码(未内存)是不言自明的:

function f(s, i, j, haveUncommon){
  if (i < 0 || j < 0)
    return haveUncommon ? 0 : -Infinity
    
  if (s[i] == s[j]){
    if (haveUncommon){
      return 1 + f(s, i-1, j-1, true)
      
    } else if (i == j){
      return Math.max(
        1 + f(s, i-1, j-1, false),
        f(s, i-1, j, false),
        f(s, i, j-1, false)
      )
    } else {
      return 1 + f(s, i-1, j-1, true)
    }
  }
    
  return Math.max(
    f(s, i-1, j, haveUncommon),
    f(s, i, j-1, haveUncommon)
  )
}

var s = "aabcde"

console.log(f(s, s.length-1, s.length-1, false))