Длина самой длинной палиндромной подпоследовательности четной длины без двух одинаковых соседних символов

Опубликовано: 5 Января, 2022

Для данной строки str задача состоит в том, чтобы найти длину самой длинной палиндромной подпоследовательности четной длины, в которой нет двух одинаковых соседних символов, кроме средних символов.

Примеры:

Input: str = “abscrcdba” 
Output:
Explanation: 
abccba is the required string which has no two consecutive characters same except the middle characters. Hence the length is 6

Input: str = “abcd” 
Output:

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы сформировать рекурсивное решение и сохранить значения подзадач с использованием динамического программирования. Для вычисления результата можно выполнить следующие шаги:

  • Сформируйте рекурсивную функцию, которая будет принимать строку и символ, который является начальным символом подпоследовательности.
  • Если первый и последний символы строки совпадают с данным символом, удалите первый и последний символы и вызовите функцию со всеми значениями символов от 'a' до 'z', кроме данного символа, поскольку соседний символ не может быть таким же и найдите максимальную длину.
  • Если первый и последний символы строки не совпадают с данным символом, тогда найдите первый и последний индекс данного символа в строке, скажем i , j соответственно. Возьмите подстроку от i до j и вызовите функцию с подстрокой и заданным символом.
  • Наконец, запомните значения в неупорядоченной карте и используйте ее, если функция снова вызывается с теми же параметрами.

Ниже приводится реализация описанного выше подхода:

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 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 + " " );
}
}
// 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 + " " );
}
}
// This code is contributed by rutvik_56
Выход
 6

Сложность времени: O (N 2 )
Вспомогательное пространство: O (N)

Статья по теме: Самая длинная палиндромная подпоследовательность

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ