Python найти сжатую строку минимальной длины с кодированием длины серии, мы можем удалить n последовательных символов, чтобы получить минимальную длину

Question

У нас есть строка 'AABCAA', если мы выполняем кодирование длины этой строки, мы получаем '2ABC2A'. длина составляет 6. У нас есть возможность удалить N последовательных символов из строки. мы должны найти сжатую строку длины строки с минимальной длиной

Необходимо найти всю подстроку, образованную удалением двух последовательных символов

'BCAA' --->BC2A --->4  
'ACAA' --->AC2A --->4  
'AAAA' --->4A --->2  
'AABA' --->2ABA ---> 4  
'AABC' --->2ABC ---> 4

, в этом ответе '4A'

Ниже это код, есть ли способ, которым мы можем достичь этого с меньшей сложностью времени и пространства ??????

'''

    **def run_len_encoding_removing_n(s,n):
        m=len(encoding(s))
        s1=encoding(s)
        for i in range(len(s)-n+1):
                #l.append(s[:i] + s[i+n :])
                print(s[:i] + s[i+n :])
                r=encoding(s[:i] + s[i+n :])
                if len(r)< m:
                    m=len(r)
                    s1=r
        print(m)
        print(s1)

    def encoding(s):
        encoded_message=""
        i=0
        while i < len(s):
            cnt=1
            j=i
            while j < len(s)-1:
                if s[j]==s[j+1]:
                    cnt=cnt+1
                    j=j+1
                else:
                    break
            encoded_message=encoded_message + str(cnt)+s[i]
            i=j+1
        return encoded_message



    if __name__ == '__main__':
        n = 2
        s = 'AABCAA'
        run_len_encoding_removing_n(s,n)**

'''

Answer 1

# space complexity O(1)
# time complexity O(n)

# greedy: we will remove the first two characters which will increase matches

def encode(s):
  to_remove = []
  for i in range(len(s)-2):

    # if match continue
    if i in to_remove:
      continue
    if s[i] == s[i+1]:
      continue
    elif s[i] == s[i+2] and len(to_remove) <= 1:
      # let's remove i+1 to increase match
      to_remove.append(i+1)
    elif s[i] == s[i+3] and len(to_remove) == 0:
      to_remove.append(i+1)
      to_remove.append(i+2)

    if len(to_remove) == 2:
      return to_remove

    else:
      if len(to_remove) == 0:
        return [0,1]
      elif len(to_remove) == 1:
        return to_remove + [len(s)-to_remove[0]]  # any choice will work

encode('AAAACAA')