Separate a string into blocks according to similarity

Question

I have the following challenge proposed:

input: "aaaaabbbbccccccaaaaa"

output : "5a4b6c7a"

And I made the following code to solve it:

def conta_numero_letras(string):
    armazena = ''
    for letra in string:
        if letra not in armazena:
            armazena += str(string.count(letra)) + letra
        else:
            pass
    return armazena

print(conta_numero_letras("aaaaabbbbccccccaaaaaaa"))

And my exit is being: 12a4b6c How do I scan by blocks the string, to get the output amount of each block individually?

Answer 1

Diovana, I made the following code to solve the problem, in it has some comments explaining how the code works:

def conta_letras(string):
  #Pego o tamanho da string para verificar string vazia e também para o loop
  tamanho = len(string)

  #String vazia, retorna vazio...
  if tamanho == 0:
    return ""

  contagem = "" #String que contém a contagem de letras, string de retorno da função
  letra_atual = string[0] #Primeira letra da string
  quantidade = 0 #Contagem de letras

  for i in range(tamanho):
    #Se a letra for a mesma da anterior, aumenta a contagem
    if letra_atual == string[i]:
      quantidade += 1
    else:
      #Se a letra mudou, adiciona a contagem e a letra a string de retorno
      contagem += str(quantidade) + letra_atual
      #Reinicia a letra atual e a contagem
      letra_atual = string[i]
      quantidade = 1

    #Caso seja a última letra do loop, finalizo a contagem
    if i == (tamanho - 1):
      contagem += str(++quantidade) + letra_atual

  return contagem

print(conta_letras("aaaaabbbbccccccaaaaaaa"))
print(conta_letras("abcdefgh"))
print(conta_letras("zzzzaaaabbbbccccbbbbaaaacccczzzz"))
print(conta_letras("xptoaaabbb___zzxzz"))

Answer 2

The problem with your code is that it counts all occurrences of a given letter in the string, regardless of its position (the value returned by the method count) - and does not take into account separate blocks with the same letter.

For the record, this algorithm is called a "run length encoding" (RLE), and is a compression algorithm still used in many basic file types that we use on a day-to-day basis (e.g., GIF images, and Postscript images).

Good - the solution is to use more state variables - to go through the letter of the original string, to be able to look "backwards" and see which is the last letter - and take an action if it is equal to the current, and another case is different.

Another thing to keep in mind is that in Python, strings are immutable objects. So, although in this case, the performance is not relevant (anyway this code will run in less than 10ms for strings smaller than 30 pages of text), it is better that the mutable code data is built in a "mutable" structureas a list, and after everything is collected, "frozen" in an output string. For this "freeze" the key is the ". Join" method of the strings, which use a list as input.

Your job can stay that way:

def rle(input_str):
   count = -1
   previous = None
   result = []
   for char in input_str:
       count += 1
       if char != previous and previous != None:
            result.append((count, previous))
            count = 0
       previous = char
   if previous:
      result.append((count + 1, previous))

   output = ''.join((str(pair[0]) + pair[1]) for pair in result)
   return output