Substring comum mais longa em JS

Apr 17 2023

Uma das perguntas mais frequentes em Frontend Interviews é encontrar a substring comum mais longa. Vamos resolver isso em Javascript simples.

DSA em Javascript

Agora observe que diz “Sub” string, o que significa que a string deve ser consecutiva. Vamos primeiro entender isso.

let s1 = "javascript";
let s2 = "java";

let s1 = "javascript";
let s2 = "scrip";

Isso foi para mostrar que você não está confundindo com a Subsequência, que é novamente outra pergunta famosa que os entrevistadores fazem. Subsequência significa que a string NÃO pode estar de maneira consecutiva. Vou explicar melhor isso em outro post.

Uma abordagem de força bruta para resolver isso seria calcular todas as possibilidades de s1, depois calcular todas as possibilidades de s2 e comparar ambas. Uma abordagem otimizada seria usar uma matriz 2-d para resolver isso. Vejamos como:

Pegaremos uma matriz 2D dp[][] e criaremos uma tabela aqui como dp[row][column] e forneceremos valores à medida que percorremos as duas strings. Tomamos s1 e s2 abaixo.

s1 = "ABCDGH"
s2 = "ACDGHR"

Estamos preenchendo a primeira linha como “0” porque se nenhum caractere estiver presente, LCS será 0. O mesmo com a primeira coluna, se nenhum caractere estiver presente em s2, então LCS será 0.

Agora, devemos começar a preencher cada caixa com valores.

Observe aqui que meus valores iniciais de "i" e "j" são 1.

Começando com a posição [1][1] , a lógica que devemos colocar para cada valor é que, se o i'ésimo elemento de s1 for igual ao j'ésimo elemento de s2 (o caractere na string encontra uma correspondência), então este valor será “valor da diagonal superior + 1”, caso contrário, apenas armazenamos 0.

Em termos de código, a condição se parece com isto:

if( s1[i - 1] == s2[j - 1] ){
  dp[i][j] = 1 + dp[i-1][j-1];
}
else {
  dp[i][j] = 0;
}

Agora, com essa lógica, a gente vai enchendo a tabela aqui, e por fim, teremos uma tabela assim,

Escrevemos 2 na posição dp[3][4] porque o caractere “D” corresponde em ambas as strings e adicionamos 1 ao seu valor diagonal que o torna 2. Usando a mesma lógica, inserimos todos os valores e 4 é o número mais alto em nossa tabela.

Nossa resposta é qualquer que seja o número mais alto em nossa tabela. Esse é o comprimento da substring comum mais longa.

Vamos criar uma solução completa em execução em JS abaixo. Vamos começar criando um array 2d, aqui estamos preenchendo os valores para cada item como 0 inicialmente:

let n1 = s1.length;
  let n2 = s2.length;
  let dp = Array(n1 + 1)
    .fill(0)
    .map(() => Array(n2 + 1).fill(0));

let s1 = "abcdgh";
let s2 = "acdghr";

function findLongestCommonSubstring(s1, s2) {
  let n1 = s1.length;
  let n2 = s2.length;
  let dp = Array(n1 + 1)
    .fill(0)
    .map(() => Array(n2 + 1).fill(0));
  let lcs = 0;
  for (let i = 1; i <= n1; i++) {
    for (let j = 1; j <= n2; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
        lcs = Math.max(lcs, dp[i][j]);
      }
    }
  }
  return lcs;
}

console.log("Ans: ", findLongestCommonSubstring(s1, s2));

Essa abordagem diminuiu muito nossa complexidade de tempo para N².

A principal razão pela qual coloquei esse famoso problema em JS é para quem procura uma solução funcional em JS, pois não consegui encontrá-lo quando comecei a trabalhar nele.

Substring comum mais longa em JS

Muito obrigado pela leitura! Certifique-se de dar um joinha abaixo. :)