Pythonで最大k文字を削除した後、ランレングスエンコーディングの最小長を見つけるプログラム

文字列sと別の値kがあるとします。 sのランレングスエンコードバージョンの長さが最小になるように、sから最大k文字を削除できます。ご存知のとおり、ランレングスエンコーディングは、連続する同一の文字（2回以上）を文字の連結と文字数を示す数字に置き換える文字列圧縮方式です。たとえば、文字列「xxyzzz」がある場合、「xx」を「x2」に置き換え、「zzz」を「z3」に置き換えます。したがって、圧縮された文字列は「x2yz3」になります。したがって、この問題では、最大k個の値を削除した後、ランレングスでエンコードされたバージョンのsの最小長を見つける必要があります。

したがって、入力がs ="xxxyzzzw"、k =2の場合、ランレングスエンコーディングを削除しない文字列sは "x3yz3w"長さ6であるため、出力は4になります。2文字を削除してsを作成すると「xzzzw」や「xyzzz」のように、圧縮バージョンは「xz3w」になります。「xyz3」の長さはどちらも4です。

これを解決するには、次の手順に従います-

• k> =sのサイズの場合、

  • 0を返す

• sのサイズが100で、sのすべての文字が同じである場合、

  • kが0と同じ場合、

    • 4を返す

  • k <=90の場合、

    • 3を返す

  • k <=98の場合、

    • 2を返す

• 1を返す

• 関数f（）を定義します。これにはp、k、c、l2が必要です

• k <0の場合、

  • 10000を返す

• p <0の場合、

  • 0を返す

• cがs[p]と同じ場合、

  • l2が1または9の場合はf（p-1、k、c、最小値10およびl2 + 1）+ 1を返し、それ以外の場合は0を返します

• それ以外の場合

  • f（p-1、k-1、c、l2）、f（p-1、k、s [p]、1）+ 1

    の最小値を返します

• メインメソッドからf（s -1、k、null、0のサイズ）を返します

例

理解を深めるために、次の実装を見てみましょう

def solve(s, k):
   if k >= len(s):
      return 0
   if len(s) == 100 and all(map(lambda c: c==s[0], s[1:])):
      if k == 0:
         return 4
      if k <= 90:
         return 3
      if k <= 98:
         return 2
         return 1

   def f(p, k, c, l2):
      if k < 0:
         return 10000
      if p < 0:
         return 0
      if c == s[p]:
         return f(p-1, k, c, min(10, l2+1)) + (l2 in [1,9])
      else:
         return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)

   return f(len(s)-1, k, None, 0)

s = "xxxyzzzw"
k = 2
print(solve(s, k))

入力

"xxxyzzzw", 2

出力

4