Superando desafios comuns relacionados a texto: a história do TypeScript

Repositório GitHub: https://github.com/ImBIOS/common-char-extractor-ts

No universo das entrevistas de programação, os desafios algorítmicos não servem apenas como testes de conhecimento técnico, mas também como janelas para a acuidade de resolução de problemas dos candidatos. Um problema intrigante, frequentemente encontrado, gira em torno da manipulação de strings - uma habilidade fundamental no arsenal de um desenvolvedor. Hoje, mergulhamos em um problema cativante: identificar caracteres comuns em várias strings e como abordamos sua solução usando TypeScript.

O Desafio Revelado

A tarefa em questão era aparentemente simples, mas enganosamente complexa: dado um array de strings, deveríamos escrever uma função que extraísse e retornasse um array de caracteres que aparecem na mesma posição em todas as strings. Por exemplo, dado a entrada ["abcd", "bcd", "cde", "cdef"], a saída esperada seria ["c", "d"], significando que 'c' e 'd' são os caracteres comuns compartilhados por todas as strings nas posições correspondentes.

Construindo a Solução

Nossa jornada começou com a escolha do TypeScript para a solução - uma decisão motivada pelo sistema de tipos robusto do TypeScript, que aumenta a confiabilidade do código e a produtividade do desenvolvedor. O passo inicial envolveu a iteração sobre cada caractere da primeira string, usando-o como referência para comparar com os caracteres correspondentes nas strings subsequentes.

/**
 * Extrai e retorna um array de caracteres que aparecem na mesma posição
 * em todas as strings dentro do array de entrada.
 *
 * @param {string[]} words - Um array de strings a serem analisadas.
 * @returns {string[]} Um array de caracteres que são comuns em todas as strings fornecidas,
 * mantendo sua ordem de aparição na primeira string.
 */
export function extractCommonLetters(words: string[]): string[] {
  if (words.length === 0) {
    return []
  }

  const copiedWords = [...words]
  const result: string[] = []
  const referenceWord = copiedWords[0]

  // Itera sobre cada caractere na primeira palavra
  for (let i = 0; i < referenceWord.length; i++) {
    const currentChar = referenceWord[i]
    let isCharCommonAcrossWords = true

    // Verifica se o caractere atual existe em cada uma das outras palavras
    for (let j = 1; j < copiedWords.length; j++) {
      const word = copiedWords[j]
      const charIndex = word.indexOf(currentChar)

      // Se o caractere não for encontrado, interrompa e defina a flag como false
      if (charIndex === -1) {
        isCharCommonAcrossWords = false
        break
      } else {
        // Remove o caractere encontrado da palavra para lidar com duplicatas
        copiedWords[j] = word.slice(0, charIndex) + word.slice(charIndex + 1)
      }
    }

    // Se o caractere é comum em todas as palavras, adicione-o ao resultado
    if (isCharCommonAcrossWords) {
      result.push(currentChar)
    }
  }

  return result
}

Este trecho encapsula a essência de nossa abordagem, enfatizando a legibilidade e a lógica direta para lidar com o problema.

Aventure-se Além: Testando a Solução

Para validar nossa solução, empregamos uma suíte de casos de teste cobrindo vários cenários - de casos básicos a mais complexos, envolvendo caracteres especiais e sensibilidade a maiúsculas e minúsculas. Esses testes completos garantiram a robustez e a correção do nosso algoritmo em uma ampla gama de entradas.

Analisando Complexidade de Espaço e Tempo

Após a reflexão, a complexidade de tempo de nossa solução é determinada principalmente pelo número de caracteres na primeira string (vamos denotar isso como N) e pelo número total de strings (denotar isso como M). Para cada caractere na primeira string, verificamos sua ocorrência na posição correspondente em todas as outras strings, levando a uma complexidade de tempo de O(N*M).

A complexidade de espaço de nossa solução é O(N), pois armazenamos os caracteres comuns em um array. No pior cenário, onde todos os caracteres são comuns em todas as strings, o tamanho desse array seria proporcional ao comprimento da primeira string.

Caminhos para Melhoria

Embora nossa solução seja eficiente para um número moderado de strings e caracteres, sempre há espaço para otimização. Aqui estão algumas estratégias para melhorar ainda mais seu desempenho:

Término Antecipado: Se em algum momento um caractere não corresponder na posição correspondente em todas as strings, podemos interromper o loop antecipadamente, economizando comparações desnecessárias.
Otimização para Strings Curtas: Começar com a string mais curta como referência pode reduzir potencialmente o número de iterações, pois minimiza o número máximo de caracteres a serem verificados.
Processamento Paralelo: Para grandes conjuntos de dados, aproveitar técnicas de processamento paralelo para comparar caracteres entre strings concorrentemente pode reduzir significativamente o tempo de execução.
Técnicas de Hash: Usar um mapa de hash para controlar as posições e ocorrências de caracteres pode oferecer uma maneira mais sofisticada de identificar caracteres comuns, especialmente ao lidar com conjuntos extensos de strings.

Pensamentos Finais

O desafio dos caracteres comuns serve como um testemunho notável da elegância dos problemas de manipulação de strings, convidando os desenvolvedores a mergulhar nas nuances de algoritmos e estruturas de dados. Por meio do TypeScript, não apenas encontramos uma solução, mas também abraçamos uma jornada de clareza, segurança de tipo e resolução de problemas eficiente.

Ao finalizarmos, é essencial lembrar que a jornada pelos desafios de codificação é tanto sobre o caminho percorrido quanto sobre o destino alcançado. Cada problema, incluindo este, oferece uma oportunidade única para refinar nossas habilidades, repensar nossas abordagens e, mais importante, continuar aprendendo.