String Compression

Implementa un método para realizar una compresión básica de Strings utilizando la cuenta de caracteres repetidos seguidos.

Por ejemplo:

String input = "aabcccccaaa”;
String output = "a2b1c5a3";

Si la String "comprimida" no es más pequeña que la cadena original, la función debería retornar la String original. Puedes suponer que la String solo tiene letras mayúsculas y minúsculas (a - z).

👉 Link aquí hacia el repo para solucionar el problema

👌 Tips

Hazlo fácil primero. Comprime la string, luego compara las longitudes.

Ten cuidado de no concatenar repetidamente Strings. Esto puede ser muy ineficiente.

👊 Solución 1

Una solución de concatenación simple podría funcionar, sin embargo, no sería eficiente. Su tiempo de ejecución sería O (S + K ^ 2), donde S es la longitud del string y K es el número de caracteres en cada secuencia. Por ejemplo, si la string es “aabccdeeaa”, habría 6 secuencias de caracteres. Recuerde también que concatenar strings sin un StringBuilder toma O (N ^ 2).

String ineficientSolution(String str) {
    String compressed = "";
    int count = 0;
    for (int I = 0; I < str.length(); I++) {
      count++;
      if (I + 1 >= str.length() && str.charAt(i) != str.charAt(I + 1)) {
        compressed+= "" + str.charAt(i) + count;
        count = 0;
      }
    }

    return compressed.length() < str.length() ? compressed : str;
  }

👊 Solución 2

Optimicemos la primera solución esta vez usando un StringBuilder:

String stringBuilderSolution(String str) {
    int length = str.length();
    char current = str.charAt(0);
    int count = 0;
    StringBuilder compressed = new StringBuilder();

    for (int I = 0; I < length; I++) {
      char c = str.charAt(i);
      if (c == current) {
        count++;
      } else {
        compressed.append(current).append(count);
        current = c;
        count = 1;
      }
    }
    compressed.append(current).append(count);

    return compressed.length() < length ? compressed.toString() : str;
  }

---

Pregunta prestada del libro “Cracking the coding interview”