Compresión de Strings

Instrucciones

Nivel de dificultar: Fácil

Fuente del problema: Cracking the coding interview

Dada una cadena de caracteres (String), crea una función que permita comprimir la cantidad de caracteres. Para esto, debes agrupar los elementos y agregarle la cantidad de veces que se repiten de forma consecutiva.

Por ejemplo:

[aaabccddd] → [a3b1c2d3]

Otra consideración es que si la nueva cadena termina teniendo más elementos que la original, debe de regresar la original.

Por ejemplo

[abcd] regresa [abcd] en vez de [a1b1c1d1]

Solución

Complejidad temporal: O(n)

Este es uno de los problemas clásicos en las entrevistas de código, ya que permite evaluar aspectos como la optimización de espacio y manejo de cadenas de caracteres.

El enfoque para dar con la solución es sencillo: recorrer todos los elementos y registrar la cantidad de veces que se repite cada elemento de manera secuencial.

Algoritmo

Hay distintas formas para resolver este problema, incluso pueden variar de acuerdo al lenguaje de programación. Sin embargo, la forma más sencilla es verificar el elemento actual y el siguiente. Es decir, si los elementos son distintos, se agrega a la nueva cadena el caracter evaluado, a´si como la cantidad de veces que se repite.

Ejemplo de la solución de forma algorítmica:

1. Declarar:
   1. Un nuevo string vacío.
   2. Variable «contador» inicializado en 0
2. Recorrer el array
   1. Incrementar el contador una unidad
   2. Si el elemento actual es diferente al elemento siguiente, o el siguiente es el último elemento de la cadena
      1. Agregar el caracter actual junto la variable «contador» al nuevo string
      2. Reiniciar el contador a 0
3. Verifica si la cadena de caracteres es igual o mayor a la original

Código

El código del problema es el siguiente.

public class Solution {

	public static String compressionString(String word) {
		    int count = 0;
		    StringBuilder newString = new StringBuilder();

		    for (int i = 0; i < word.length(); i++) {
		        count++;
		        if(i + 1 >= word.length() ||  word.charAt(i) != word.charAt(i + 1)) {
		            newString.append(word.charAt(i) + "" + count);
		            count = 0;
		        }
		    } 
		    return newString.length() >= word.length() ? word : newString.toString();
		}
}