Dada una string str , la tarea es encontrar la longitud de la subsecuencia palindrómica más larga de longitud uniforme sin dos caracteres adyacentes iguales excepto los del medio.
Ejemplos:
Entrada: str = “abscrcdba”
Salida: 6
Explicación:
abccba es la string requerida que no tiene dos caracteres consecutivos iguales excepto los caracteres del medio. Por lo tanto, la longitud es 6Entrada: str = “abcd”
Salida: 0
Enfoque: La idea es formar una solución recursiva y almacenar los valores de los subproblemas usando Programación Dinámica . Se pueden seguir los siguientes pasos para calcular el resultado:
- Forme una función recursiva que tomará una string y un carácter que es el carácter inicial de la subsecuencia.
- Si el primer y último carácter de la string coincide con el carácter dado, elimine el primer y último carácter y llame a la función con todos los valores de carácter de ‘a’ a ‘z’ excepto el carácter dado, ya que el carácter adyacente no puede ser el mismo y encuentre la longitud máxima.
- Si el primer y último carácter de la string no coincide con el carácter dado, busque el primer y último índice del carácter dado en la string, digamos i , j respectivamente. Tome la substring de i a j y llame a la función con la substring y el carácter dado.
- Finalmente, memorice los valores en un mapa desordenado y utilícelo si la función se vuelve a llamar con los mismos parámetros.
La siguiente es la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
// To store the values of subproblems
unordered_map<string, lli> dp;
// Function to find the
// Longest Palindromic subsequence of even
// length with no two adjacent characters same
lli solve(string s, char c)
{
// Base cases
// If the string length is 1 return 0
if (s.length() == 1)
return 0;
// If the string length is 2
if (s.length() == 2) {
// Check if the characters match
if (s[0] == s[1] && s[0] == c)
return 1;
else
return 0;
}
// If the value with given parameters is
// previously calculated
if (dp[s + " " + c])
return dp[s + " " + c];
lli ans = 0;
// If the first and last character of the
// string matches with the given character
if (s[0] == s[s.length() - 1] && s[0] == c)
{
// Remove the first and last character
// and call the function for all characters
for (char c1 = 'a'; c1 <= 'z'; c1++)
if (c1 != c)
ans = max(
ans,
1 + solve(s.substr(1,
s.length() - 2),
c1));
}
// If it does not match
else {
// Then find the first and last index of
// given character in the given string
for (lli i = 0; i < s.length(); i++)
{
if (s[i] == c)
{
for (lli j = s.length() - 1; j > i; j--)
if (s[j] == c)
{
if (j == i)
break;
// Take the substring from i
// to j and call the function
// with substring
// and the given character
ans = solve(s.substr(i, j - i + 1),
c);
break;
}
break;
}
}
}
// Store the answer for future use
dp[s + " " + c] = ans;
return dp[s + " " + c];
}
// Driver code
int main()
{
string s = "abscrcdba";
lli ma = 0;
// Check for all starting characters
for (char c1 = 'a'; c1 <= 'z'; c1++)
ma = max(ma, solve(s, c1) * 2);
cout << ma << endl;
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
class GFG {
// To store the values of subproblems
static Map<String, Integer> dp = new HashMap<>();
// Function to find the
// Longest Palindromic subsequence of even
// length with no two adjacent characters same
static Integer solve(char[] s, char c)
{
// Base cases
// If the String length is 1 return 0
if (s.length == 1)
return 0;
// If the String length is 2
if (s.length == 2) {
// Check if the characters match
if (s[0] == s[1] && s[0] == c)
return 1;
else
return 0;
}
// If the value with given parameters is
// previously calculated
if (dp.containsKey(String.valueOf(s) + " " + c))
return dp.get(String.valueOf(s) + " " + c);
Integer ans = 0;
// If the first and last character of the
// String matches with the given character
if (s[0] == s[s.length - 1] && s[0] == c)
{
// Remove the first and last character
// and call the function for all characters
for (char c1 = 'a'; c1 <= 'z'; c1++)
if (c1 != c)
ans = Math.max(
ans,
1 + solve(Arrays.copyOfRange(
s, 1,
s.length - 1),
c1));
}
// If it does not match
else {
// Then find the first and last index of
// given character in the given String
for (Integer i = 0; i < s.length; i++)
{
if (s[i] == c)
{
for (Integer j = s.length - 1;
j > i;
j--)
if (s[j] == c)
{
if (j == i)
break;
// Take the subString from i
// to j and call the function
// with subString
// and the given character
ans = solve(Arrays.copyOfRange(
s, i,
j + 1),
c);
break;
}
break;
}
}
}
// Store the answer for future use
dp.put(String.valueOf(s) + " " + c, ans);
return dp.get(String.valueOf(s) + " " + c);
}
// Driver code
public static void main(String[] args)
{
String s = "abscrcdba";
Integer ma = 0;
// Check for all starting characters
for (char c1 = 'a'; c1 <= 'z'; c1++)
ma = Math.max(ma,
solve(s.toCharArray(), c1) * 2);
System.out.print(ma + "\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of above approach
# To store the values of subproblems
dp = {}
# Function to find the
# Longest Palindromic subsequence of even
# length with no two adjacent characters same
def solve(s, c):
# Base cases
# If the string length is 1 return 0
if (len(s) == 1):
return 0
# If the string length is 2
if (len(s) == 2):
# Check if the characters match
if (s[0] == s[1] and s[0] == c):
return 1
else:
return 0
# If the value with given parameters is
# previously calculated
if (s + " " + c) in dp:
return dp[s + " " + c]
ans = 0
# If the first and last character of the
# string matches with the given character
if (s[0] == s[len(s) - 1] and s[0] == c):
# Remove the first and last character
# and call the function for all characters
for c1 in range(97, 123):
if (chr(c1) != c):
ans = max(ans, 1 + solve(
s[1: len(s) - 1], chr(c1)))
# If it does not match
else:
# Then find the first and last index of
# given character in the given string
for i in range(len(s)):
if (s[i] == c):
for j in range(len(s) - 1, i, -1):
if (s[j] == c):
if (j == i):
break
# Take the substring from i
# to j and call the function
# with substring
# and the given character
ans = solve(s[i: j - i + 2], c)
break
break
# Store the answer for future use
dp[s + " " + c] = ans
return dp[s + " " + c]
# Driver code
if __name__ == "__main__":
s = "abscrcdba"
ma = 0
# Check for all starting characters
for c1 in range(97, 123):
ma = max(ma, solve(s, chr(c1)) * 2)
print(ma)
# This code is contributed by AnkitRai01
C#
// C# implementation of
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
// To store the values of subproblems
static Dictionary<string, int> dp
= new Dictionary<string, int>();
// Function to find the
// Longest Palindromic subsequence of even
// length with no two adjacent characters same
static int solve(char[] s, char c)
{
// Base cases
// If the String length is 1 return 0
if (s.Length == 1)
return 0;
// If the String length is 2
if (s.Length == 2) {
// Check if the characters match
if (s[0] == s[1] && s[0] == c)
return 1;
else
return 0;
}
// If the value with given parameters is
// previously calculated
if (dp.ContainsKey(new string(s) + " " + c))
return dp[new string(s) + " " + c];
int ans = 0;
// If the first and last character of the
// String matches with the given character
if (s[0] == s[s.Length - 1] && s[0] == c)
{
// Remove the first and last character
// and call the function for all characters
for (char c1 = 'a'; c1 <= 'z'; c1++)
if (c1 != c) {
int len = s.Length - 2;
char[] tmp = new char[len];
Array.Copy(s, 1, tmp, 0, len);
ans = Math.Max(ans, 1 + solve(tmp, c1));
}
}
// If it does not match
else {
// Then find the first and last index of
// given character in the given String
for (int i = 0; i < s.Length; i++)
{
if (s[i] == c)
{
for (int j = s.Length - 1; j > i; j--)
if (s[j] == c)
{
if (j == i)
break;
// Take the subString from i
// to j and call the function
// with subString and the
// given character
int len = j + 1 - i;
char[] tmp = new char[len];
Array.Copy(s, i, tmp, 0, len);
ans = solve(tmp, c);
break;
}
break;
}
}
}
// Store the answer for future use
dp[new string(s) + " " + c] = ans;
return dp[new string(s) + " " + c];
}
// Driver Code
public static void Main(string[] args)
{
string s = "abscrcdba";
int ma = 0;
// Check for all starting characters
for (char c1 = 'a'; c1 <= 'z'; c1++)
ma = Math.Max(ma,
solve(s.ToCharArray(), c1) * 2);
Console.Write(ma + "\n");
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation of above approach
// To store the values of subproblems
var dp = new Map();
// Function to find the
// Longest Palindromic subsequence of even
// length with no two adjacent characters same
function solve(s, c)
{
// Base cases
// If the string length is 1 return 0
if (s.length == 1)
return 0;
// If the string length is 2
if (s.length == 2) {
// Check if the characters match
if (s[0] == s[1] && s[0] == c)
return 1;
else
return 0;
}
// If the value with given parameters is
// previously calculated
if (dp.has(s + " " + c))
return dp.get(s + " " + c);
var ans = 0;
// If the first and last character of the
// string matches with the given character
if (s[0] == s[s.length - 1] && s[0] == c)
{
// Remove the first and last character
// and call the function for all characters
for (var c1 = 'a'.charCodeAt(0); c1 <= 'z'.charCodeAt(0); c1++)
if (String.fromCharCode(c1) != c)
ans = Math.max(
ans,
1 + solve(s.substring(1,
s.length - 1),
String.fromCharCode(c1)));
}
// If it does not match
else {
// Then find the first and last index of
// given character in the given string
for (var i = 0; i < s.length; i++)
{
if (s[i] == c)
{
for (var j = s.length - 1; j > i; j--)
if (s[j] == c)
{
if (j == i)
break;
// Take the substring from i
// to j and call the function
// with substring
// and the given character
ans = solve(s.substring(i, j + 1),
c);
break;
}
break;
}
}
}
// Store the answer for future use
dp.set(s + " " + c, ans);
return ans;
}
// Driver code
var s = "abscrcdba";
var ma = 0;
// Check for all starting characters
for (var c1 = 'a'.charCodeAt(0); c1 <= 'z'.charCodeAt(0); c1++)
ma = Math.max(ma, solve(s, String.fromCharCode(c1)) * 2);
document.write(ma);
</script>
Producción
6
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Artículo Relacionado: Subsecuencia palindrómica más larga
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA