Declaración del problema:

Dada una matriz de caracteres, comprímala usando el siguiente algoritmo:

• Comience con una cadena vacía s.
• Para cada grupo de caracteres repetidos consecutivos en caracteres:
  • Si la longitud del grupo es 1, agregue el carácter a s.
  • De lo contrario, agregue el carácter seguido de la longitud del grupo.

La cadena comprimida s no debe devolverse por separado, sino que debe almacenarse en los caracteres de la matriz de caracteres de entrada. Tenga en cuenta que las longitudes de grupo de 10 o más se dividirán en varios caracteres en caracteres.

Una vez que haya terminado de modificar la matriz de entrada, devuelva la nueva longitud de la matriz.

Debes escribir un algoritmo que utilice solo espacio adicional constante.

Ejemplo 1:

• Entrada: caracteres = ["a","a","b","b","c","c","c"]
• Salida: Devuelve 6, y los primeros 6 caracteres de la matriz de entrada deben ser: ["a","2","b","2","c","3"]
• Explicación: Los grupos son "aa", "bb" y "ccc". Esto se comprime a "a2b2c3".

Ejemplo 2:

• Entrada: caracteres = ["a"]
• Salida: Devuelve 1, y el primer carácter de la matriz de entrada debe ser: ["a"]
• Explicación: El único grupo es "a", que permanece sin comprimir ya que es un solo carácter.

Ejemplo 3:

• Entrada: caracteres = ["a","b","b","b","b","b","b","b","b","b","b ","cama y desayuno"]
• Salida: Devuelve 4, y los primeros 4 caracteres de la matriz de entrada deben ser: ["a","b","1","2"]
• Explicación: Los grupos son "a" y "bbbbbbbbbbbb". Esto se comprime a "ab12".

Restricciones:

• 1
• chars[i] es una letra inglesa minúscula, una letra mayúscula, un dígito o un símbolo en inglés.

Proceso de pensamiento inicial:

Para resolver este problema, necesitamos iterar a través de la matriz mientras realizamos un seguimiento del carácter actual y su recuento. Cuando encontramos un nuevo carácter, agregamos el carácter actual y su recuento (si es mayor que 1) a la matriz. Necesitamos asegurarnos de hacer esto en el lugar para cumplir con el requisito de complejidad del espacio.

Solución básica (fuerza bruta):

La solución de fuerza bruta implica la creación de una nueva matriz para almacenar la versión comprimida de la matriz de entrada. Esto no ahorra espacio, pero nos ayuda a comprender los pasos necesarios.

Código:

function compressBruteForce(chars: string[]): number {
    const n = chars.length;
    let compressed: string[] = [];
    let i = 0;

    while (i  1) {
            compressed.push(...count.toString().split(''));
        }
    }

    for (let j = 0; j 




  
  
  Análisis de complejidad temporal:

• Complejidad del tiempo: O(n), donde n es la longitud de la matriz. Repetimos la matriz una vez para contar caracteres y otra vez para escribir el resultado.
• Complejidad del espacio: O(n), ya que usamos espacio adicional para la matriz comprimida.

Limitaciones:

La solución de fuerza bruta no ahorra espacio y no cumple con la restricción de utilizar solo espacio adicional constante.

Solución optimizada:

La solución optimizada implica modificar la matriz de entrada existente para almacenar la versión comprimida. Usamos dos punteros: uno para leer la matriz de entrada y otro para escribir la salida comprimida.

Código:

function compress(chars: string[]): number {
    let writeIndex = 0;
    let i = 0;

    while (i  1) {
            let countStr = count.toString();
            for (let j = 0; j 




  
  
  Análisis de complejidad temporal:

• Complejidad del tiempo: O(n), donde n es la longitud de la matriz. Repetimos la matriz una vez para contar caracteres y otra vez para escribir el resultado.
• Complejidad del espacio: O(1), ya que usamos solo una cantidad constante de espacio adicional para las variables.

Mejoras con respecto a la solución básica:

• La solución optimizada reduce la complejidad del espacio a O(1) modificando la matriz de entrada existente.

Casos extremos y pruebas:

Casos extremos:

1. La matriz contiene solo un carácter.
2. La matriz no contiene caracteres repetidos consecutivos.
3. La matriz contiene una gran cantidad de caracteres repetidos consecutivos.

Casos de prueba:

console.log(compressBruteForce(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compressBruteForce(["a"])); // 1, ["a"]
console.log(compressBruteForce(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compressBruteForce(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compressBruteForce(["a","b","c"])); // 3, ["a","b","c"]

console.log(compress(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compress(["a"])); // 1, ["a"]
console.log(compress(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compress(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compress(["a","b","c"])); // 3, ["a","b","c"]

Estrategias generales para la resolución de problemas:

1. Comprenda el problema: Lea atentamente el enunciado del problema para comprender los requisitos y restricciones.
2. Identificar operaciones clave: Determine las operaciones clave necesarias, como contar caracteres consecutivos y modificar la matriz existente.
3. Optimizar para lograr eficiencia: Utilice algoritmos y estructuras de datos eficientes para minimizar la complejidad del tiempo y el espacio.
4. Pruebe minuciosamente: Pruebe la solución con varios casos, incluidos casos extremos, para garantizar la corrección.

Identificación de problemas similares:

1. Manipulación de cadenas:

   • Problemas en los que es necesario modificar cadenas en función de condiciones específicas.
   • Ejemplo: eliminar duplicados de una cadena.

2. Algoritmos locales:

   • Problemas donde las operaciones deben realizarse en el lugar con espacio adicional limitado.
   • Ejemplo: eliminar elementos de una matriz sin espacio adicional.

Conclusión:

• El problema de comprimir una matriz de caracteres se puede resolver de manera eficiente utilizando tanto un enfoque de fuerza bruta como un enfoque optimizado in situ.
• Comprender el problema y dividirlo en partes manejables es crucial.
• El uso de algoritmos eficientes garantiza que la solución sea óptima para entradas grandes.
• Las pruebas con varios casos extremos garantizan la solidez.
• Reconocer patrones en los problemas puede ayudar a aplicar soluciones similares a otros desafíos.

Al practicar estos problemas y estrategias, puedes mejorar tus habilidades de resolución de problemas y estar mejor preparado para diversos desafíos de codificación.