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

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

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

Примеры:

Input: str = “abscrcdba” 
Output: 6 
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: 1 

Рекомендуется: сначала попробуйте свой подход в {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.

Technical Scripter Структуры данных

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

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023