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”