Dada uma string s consistindo apenas de letras minúsculas em inglês, encontre o mínimo número de caracteres que precisam ser adicionado para o frente de s para torná-lo um palíndromo.
Observação: Um palíndromo é uma string que lê a mesma coisa para frente e para trás.
Exemplos:
Entrada :s = 'abc'
Saída : 2
Explicação : Podemos transformar a string acima em palíndromo como 'cbabc' adicionando 'b' e 'c' na frente.Entrada :s = 'aacecaaaa'
Saída : 2
Explicação : Podemos transformar a string acima em um palíndromo como 'aaaacecaaaa' adicionando dois as na frente da string.
Índice
- [Abordagem Naive] Verificando todos os prefixos - O(n^2) Tempo e O(1) Espaço
- [Abordagem esperada 1] Usando matriz lps do algoritmo KMP - O(n) Tempo e O(n) Espaço
- [Abordagem Esperada 2] Usando o Algoritmo de Manacher
[Abordagem Naive] Verificando todos os prefixos - O(n^2) Tempo e O(1) Espaço
A ideia é baseada na observação de que precisamos encontrar o prefixo mais longo de uma determinada string que também é um palíndromo. Então, o mínimo de caracteres frontais a serem adicionados para formar um determinado palíndromo de string serão os caracteres restantes.
C++ #include
#include
class GfG { // function to check if the substring // s[i...j] is a palindrome static boolean isPalindrome(String s int i int j) { while (i < j) { // if characters at the ends are not the same // it's not a palindrome if (s.charAt(i) != s.charAt(j)) { return false; } i++; j--; } return true; } static int minChar(String s) { int cnt = 0; int i = s.length() - 1; // iterate from the end of the string checking for the // longest palindrome starting from the beginning while (i >= 0 && !isPalindrome(s 0 i)) { i--; cnt++; } return cnt; } public static void main(String[] args) { String s = 'aacecaaaa'; System.out.println(minChar(s)); } }
# function to check if the substring s[i...j] is a palindrome def isPalindrome(s i j): while i < j: # if characters at the ends are not the same # it's not a palindrome if s[i] != s[j]: return False i += 1 j -= 1 return True def minChar(s): cnt = 0 i = len(s) - 1 # iterate from the end of the string checking for the # longest palindrome starting from the beginning while i >= 0 and not isPalindrome(s 0 i): i -= 1 cnt += 1 return cnt if __name__ == '__main__': s = 'aacecaaaa' print(minChar(s))
using System; class GfG { // function to check if the substring s[i...j] is a palindrome static bool isPalindrome(string s int i int j) { while (i < j) { // if characters at the ends are not the same // it's not a palindrome if (s[i] != s[j]) { return false; } i++; j--; } return true; } static int minChar(string s) { int cnt = 0; int i = s.Length - 1; // iterate from the end of the string checking for the longest // palindrome starting from the beginning while (i >= 0 && !isPalindrome(s 0 i)) { i--; cnt++; } return cnt; } static void Main() { string s = 'aacecaaaa'; Console.WriteLine(minChar(s)); } }
// function to check if the substring s[i...j] is a palindrome function isPalindrome(s i j) { while (i < j) { // if characters at the ends are not the same // it's not a palindrome if (s[i] !== s[j]) { return false; } i++; j--; } return true; } function minChar(s) { let cnt = 0; let i = s.length - 1; // iterate from the end of the string checking for the // longest palindrome starting from the beginning while (i >= 0 && !isPalindrome(s 0 i)) { i--; cnt++; } return cnt; } // Driver code let s = 'aacecaaaa'; console.log(minChar(s));
Saída
2
[Abordagem esperada 1] Usando matriz lps do algoritmo KMP - O(n) Tempo e O(n) Espaço
A observação principal é que o prefixo palindrômico mais longo de uma string se torna o sufixo palindrômico mais longo de seu reverso.
Dada uma string s = 'aacecaaaa', seu reverso revS = 'aaaacecaa'. O prefixo palindrômico mais longo de s é 'aacecaa'.
Para encontrar isso de forma eficiente, usamos o array LPS do Algoritmo KMP . Concatenamos a string original com um caractere especial e seu reverso: s + '$' + revS.
A matriz LPS para esta string combinada ajuda a identificar o prefixo mais longo de s que corresponde a um sufixo de revS que também representa o prefixo palindrômico de s.
O último valor do array LPS nos diz quantos caracteres já formam um palíndromo no início. Assim, o número mínimo de caracteres a serem adicionados para tornar s um palíndromo é s.length() - lps.back().
C++#include
import java.util.ArrayList; class GfG { static int[] computeLPSArray(String pat) { int n = pat.length(); int[] lps = new int[n]; // lps[0] is always 0 lps[0] = 0; int len = 0; // loop calculates lps[i] for i = 1 to n-1 int i = 1; while (i < n) { // if the characters match increment len // and set lps[i] if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if (len != 0) { len = lps[len - 1]; } // no prefix matches set lps[i] to 0 else { lps[i] = 0; i++; } } } return lps; } // returns minimum character to be added at // front to make string palindrome static int minChar(String s) { int n = s.length(); String rev = new StringBuilder(s).reverse().toString(); // get concatenation of string special character // and reverse string s = s + '$' + rev; // get LPS array of this concatenated string int[] lps = computeLPSArray(s); // by subtracting last entry of lps array from // string length we will get our result return (n - lps[lps.length - 1]); } public static void main(String[] args) { String s = 'aacecaaaa'; System.out.println(minChar(s)); } }
def computeLPSArray(pat): n = len(pat) lps = [0] * n # lps[0] is always 0 len_lps = 0 # loop calculates lps[i] for i = 1 to n-1 i = 1 while i < n: # if the characters match increment len # and set lps[i] if pat[i] == pat[len_lps]: len_lps += 1 lps[i] = len_lps i += 1 # if there is a mismatch else: # if len is not zero update len to # the last known prefix length if len_lps != 0: len_lps = lps[len_lps - 1] # no prefix matches set lps[i] to 0 else: lps[i] = 0 i += 1 return lps # returns minimum character to be added at # front to make string palindrome def minChar(s): n = len(s) rev = s[::-1] # get concatenation of string special character # and reverse string s = s + '$' + rev # get LPS array of this concatenated string lps = computeLPSArray(s) # by subtracting last entry of lps array from # string length we will get our result return n - lps[-1] if __name__ == '__main__': s = 'aacecaaaa' print(minChar(s))
using System; class GfG { static int[] computeLPSArray(string pat) { int n = pat.Length; int[] lps = new int[n]; // lps[0] is always 0 lps[0] = 0; int len = 0; // loop calculates lps[i] for i = 1 to n-1 int i = 1; while (i < n) { // if the characters match increment len // and set lps[i] if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if (len != 0) { len = lps[len - 1]; } // no prefix matches set lps[i] to 0 else { lps[i] = 0; i++; } } } return lps; } // minimum character to be added at // front to make string palindrome static int minChar(string s) { int n = s.Length; char[] charArray = s.ToCharArray(); Array.Reverse(charArray); string rev = new string(charArray); // get concatenation of string special character // and reverse string s = s + '$' + rev; // get LPS array of this concatenated string int[] lps = computeLPSArray(s); // by subtracting last entry of lps array from // string length we will get our result return n - lps[lps.Length - 1]; } static void Main() { string s = 'aacecaaaa'; Console.WriteLine(minChar(s)); } }
function computeLPSArray(pat) { let n = pat.length; let lps = new Array(n).fill(0); // lps[0] is always 0 let len = 0; // loop calculates lps[i] for i = 1 to n-1 let i = 1; while (i < n) { // if the characters match increment len // and set lps[i] if (pat[i] === pat[len]) { len++; lps[i] = len; i++; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if (len !== 0) { len = lps[len - 1]; } // no prefix matches set lps[i] to 0 else { lps[i] = 0; i++; } } } return lps; } // returns minimum character to be added at // front to make string palindrome function minChar(s) { let n = s.length; let rev = s.split('').reverse().join(''); // get concatenation of string special character // and reverse string s = s + '$' + rev; // get LPS array of this concatenated string let lps = computeLPSArray(s); // by subtracting last entry of lps array from // string length we will get our result return n - lps[lps.length - 1]; } // Driver Code let s = 'aacecaaaa'; console.log(minChar(s));
Saída
2
[Abordagem Esperada 2] Usando o Algoritmo de Manacher
C++A ideia é usar Algoritmo de Manacher para encontrar com eficiência todas as substrings palindrômicas em tempo linear.
Transformamos a string inserindo caracteres especiais (#) para lidar uniformemente com palíndromos de comprimento par e ímpar.
Após o pré-processamento, verificamos a partir do final da string original e usamos o array radius do palíndromo para verificar se o prefixo s[0...i] é um palíndromo. O primeiro índice i nos fornece o prefixo palindrômico mais longo e retornamos n - (i + 1) como os caracteres mínimos a serem adicionados.
#include
class GfG { // manacher's algorithm for finding longest // palindromic substrings static class manacher { // array to store palindrome lengths centered // at each position int[] p; // modified string with separators and sentinels String ms; manacher(String s) { StringBuilder sb = new StringBuilder('@'); for (char c : s.toCharArray()) { sb.append('#').append(c); } sb.append('#$'); ms = sb.toString(); runManacher(); } // core Manacher's algorithm void runManacher() { int n = ms.length(); p = new int[n]; int l = 0 r = 0; for (int i = 1; i < n - 1; ++i) { if (i < r) p[i] = Math.min(r - i p[r + l - i]); // expand around the current center while (ms.charAt(i + 1 + p[i]) == ms.charAt(i - 1 - p[i])) p[i]++; // update center if palindrome goes beyond // current right boundary if (i + p[i] > r) { l = i - p[i]; r = i + p[i]; } } } // returns the length of the longest palindrome // centered at given position int getLongest(int cen int odd) { int pos = 2 * cen + 2 + (odd == 0 ? 1 : 0); return p[pos]; } // checks whether substring s[l...r] is a palindrome boolean check(int l int r) { int len = r - l + 1; int longest = getLongest((l + r) / 2 len % 2); return len <= longest; } } // returns the minimum number of characters to add at the // front to make the given string a palindrome static int minChar(String s) { int n = s.length(); manacher m = new manacher(s); // scan from the end to find the longest // palindromic prefix for (int i = n - 1; i >= 0; --i) { if (m.check(0 i)) return n - (i + 1); } return n - 1; } public static void main(String[] args) { String s = 'aacecaaaa'; System.out.println(minChar(s)); } }
# manacher's algorithm for finding longest # palindromic substrings class manacher: # array to store palindrome lengths centered # at each position def __init__(self s): # modified string with separators and sentinels self.ms = '@' for c in s: self.ms += '#' + c self.ms += '#$' self.p = [] self.runManacher() # core Manacher's algorithm def runManacher(self): n = len(self.ms) self.p = [0] * n l = r = 0 for i in range(1 n - 1): if i < r: self.p[i] = min(r - i self.p[r + l - i]) # expand around the current center while self.ms[i + 1 + self.p[i]] == self.ms[i - 1 - self.p[i]]: self.p[i] += 1 # update center if palindrome goes beyond # current right boundary if i + self.p[i] > r: l = i - self.p[i] r = i + self.p[i] # returns the length of the longest palindrome # centered at given position def getLongest(self cen odd): pos = 2 * cen + 2 + (0 if odd else 1) return self.p[pos] # checks whether substring s[l...r] is a palindrome def check(self l r): length = r - l + 1 longest = self.getLongest((l + r) // 2 length % 2) return length <= longest # returns the minimum number of characters to add at the # front to make the given string a palindrome def minChar(s): n = len(s) m = manacher(s) # scan from the end to find the longest # palindromic prefix for i in range(n - 1 -1 -1): if m.check(0 i): return n - (i + 1) return n - 1 if __name__ == '__main__': s = 'aacecaaaa' print(minChar(s))
using System; class GfG { // manacher's algorithm for finding longest // palindromic substrings class manacher { // array to store palindrome lengths centered // at each position public int[] p; // modified string with separators and sentinels public string ms; public manacher(string s) { ms = '@'; foreach (char c in s) { ms += '#' + c; } ms += '#$'; runManacher(); } // core Manacher's algorithm void runManacher() { int n = ms.Length; p = new int[n]; int l = 0 r = 0; for (int i = 1; i < n - 1; ++i) { if (i < r) p[i] = Math.Min(r - i p[r + l - i]); // expand around the current center while (ms[i + 1 + p[i]] == ms[i - 1 - p[i]]) p[i]++; // update center if palindrome goes beyond // current right boundary if (i + p[i] > r) { l = i - p[i]; r = i + p[i]; } } } // returns the length of the longest palindrome // centered at given position public int getLongest(int cen int odd) { int pos = 2 * cen + 2 + (odd == 0 ? 1 : 0); return p[pos]; } // checks whether substring s[l...r] is a palindrome public bool check(int l int r) { int len = r - l + 1; int longest = getLongest((l + r) / 2 len % 2); return len <= longest; } } // returns the minimum number of characters to add at the // front to make the given string a palindrome static int minChar(string s) { int n = s.Length; manacher m = new manacher(s); // scan from the end to find the longest // palindromic prefix for (int i = n - 1; i >= 0; --i) { if (m.check(0 i)) return n - (i + 1); } return n - 1; } static void Main() { string s = 'aacecaaaa'; Console.WriteLine(minChar(s)); } }
// manacher's algorithm for finding longest // palindromic substrings class manacher { // array to store palindrome lengths centered // at each position constructor(s) { // modified string with separators and sentinels this.ms = '@'; for (let c of s) { this.ms += '#' + c; } this.ms += '#$'; this.p = []; this.runManacher(); } // core Manacher's algorithm runManacher() { const n = this.ms.length; this.p = new Array(n).fill(0); let l = 0 r = 0; for (let i = 1; i < n - 1; ++i) { if (i < r) this.p[i] = Math.min(r - i this.p[r + l - i]); // expand around the current center while (this.ms[i + 1 + this.p[i]] === this.ms[i - 1 - this.p[i]]) this.p[i]++; // update center if palindrome goes beyond // current right boundary if (i + this.p[i] > r) { l = i - this.p[i]; r = i + this.p[i]; } } } // returns the length of the longest palindrome // centered at given position getLongest(cen odd) { const pos = 2 * cen + 2 + (odd === 0 ? 1 : 0); return this.p[pos]; } // checks whether substring s[l...r] is a palindrome check(l r) { const len = r - l + 1; const longest = this.getLongest(Math.floor((l + r) / 2) len % 2); return len <= longest; } } // returns the minimum number of characters to add at the // front to make the given string a palindrome function minChar(s) { const n = s.length; const m = new manacher(s); // scan from the end to find the longest // palindromic prefix for (let i = n - 1; i >= 0; --i) { if (m.check(0 i)) return n - (i + 1); } return n - 1; } // Driver Code const s = 'aacecaaaa'; console.log(minChar(s));
Saída
2
Complexidade de tempo: O algoritmo de O(n) manacher é executado em tempo linear expandindo palíndromos em cada centro sem revisitar caracteres e o loop de verificação de prefixo executa O(1) operações por caractere em n caracteres.
Espaço Auxiliar: O(n) usado para a string modificada e a matriz de comprimento do palíndromo p[] que crescem linearmente com o tamanho da entrada.