Escreva uma função que retorne o palíndromo mais longo em uma determinada string

por exemplo "ccddcc" na cadeia "abaccddccefe"

Eu pensei em uma solução, mas ela é executada em O (n ^ 2) time

Algo 1:

Passos: É um método de força bruta

Tenha 2 para loops
para i = 1 a i menor que array.length -1
para j = i + 1 a j menor que array.length Desta forma, você pode obter substring de todas as combinações possíveis da matrizTenha uma função palíndromo que verifica se uma sequência é palíndromoso para cada substring (i, j) chama essa função, se for um palíndromo, armazene-o em uma variável de sequênciaSe você encontrar a próxima substring do palíndromo e se for maior que a atual, substitua-a pela atua Finalmente, sua variável de string terá a resposta

Questões: 1. Esse algo é executado no tempo O (n ^ 2

Algo 2:

Inverta a string e armazene-a em uma matriz diferenteAgora, encontre a maior substring correspondente entre a matrizMas isso também é executado no tempo O (n ^ 2)

Vocês podem pensar em algo que roda em um tempo melhor. Se possível O (n) time

questionAnswers(21)

yourAnswerToTheQuestion