Dada una string S de letras minúsculas, la tarea es encontrar la longitud de la subsecuencia palindrómica más larga compuesta únicamente por dos caracteres distintos.
Ejemplos:
Entrada: S = “bbccdcbb”
Salida: 7
Explicación:
La subsecuencia palindrómica más larga de la forma deseada es “bbcccbb”, que tiene una longitud de 7.
Entrada: S = “aeea”
Salida: 4
Explicación:
La subsecuencia palindrómica más larga de la forma deseada es “aeea”, que tiene una longitud de 4.
Enfoque:
Para resolver el problema, debemos seguir los siguientes pasos:
- Almacene el número de ocurrencias de cada carácter en una array de prefijos y también almacene la posición de cada carácter en otra array.
- Ahora, para cada par de caracteres iguales, calcule el número máximo de ocurrencias de un carácter entre ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find Longest
// Palindromic Subsequence consisting
// of two distinct characters only
#include <bits/stdc++.h>
using namespace std;
// Function that prints the length of
// maximum required subsequence
void longestPalindrome(string s)
{
// Calculate length of string
int n = s.length();
vector<vector<int> > pref(26, vector<int>(n, 0));
vector<vector<int> > pos(26);
pref[s[0] - 'a'][0]++;
pos[s[0] - 'a'].push_back(0);
// Store number of occurrences of each
// character and position of each
// character in string
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++)
pref[j][i] += pref[j][i - 1];
int index = s[i] - 'a';
pref[index][i]++;
pos[index].push_back(i);
}
int ans = 0;
// Iterate all characters
for (int i = 0; i < 26; i++) {
// Calculate number of
// occurrences of the
// current character
int size = pos[i].size();
ans = max(ans, size);
// Iterate half of the
// number of positions
// of current character
for (int j = 0; j < size / 2; j++) {
int l = pos[i][j];
int r = pos[i][size - j - 1] - 1;
// Determine maximum length
// of a character between
// l and r position
for (int k = 0; k < 26; k++) {
int sum = pref[k][r] - pref[k][l];
// Compute the maximum from all
ans = max(ans, 2 * (j + 1) + sum);
}
}
}
// Printing maximum length
cout << ans << "\n";
}
// Driver Code
int main()
{
string S = "bbccdcbb";
longestPalindrome(S);
return 0;
}
Java
// Java implementation to find Longest
// Palindromic Subsequence consisting
// of two distinct characters only
import java.util.*;
class GFG {
// Function that prints the length of
// maximum required subsequence
static void longestPalindrome(String s)
{
// Calculate length of String
int n = s.length();
int[][] pref = new int[26][n];
Vector<Integer>[] pos = new Vector[26];
for (int i = 0; i < pos.length; i++)
pos[i] = new Vector<Integer>();
pref[s.charAt(0) - 'a'][0]++;
pos[s.charAt(0) - 'a'].add(0);
// Store number of occurrences of each
// character and position of each
// character in String
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++)
pref[j][i] += pref[j][i - 1];
int index = s.charAt(i) - 'a';
pref[index][i]++;
pos[index].add(i);
}
int ans = 0;
// Iterate all characters
for (int i = 0; i < 26; i++) {
// Calculate number of
// occurences of the
// current character
int size = pos[i].size();
ans = Math.max(ans, size);
// Iterate half of the
// number of positions
// of current character
for (int j = 0; j < size / 2; j++) {
int l = pos[i].elementAt(j);
int r = pos[i].elementAt(size - j - 1) - 1;
// Determine maximum length
// of a character between
// l and r position
for (int k = 0; k < 26; k++) {
int sum = pref[k][r] - pref[k][l];
// Compute the maximum from all
ans = Math.max(ans, 2 * (j + 1) + sum);
}
}
}
// Printing maximum length
System.out.print(ans + "\n");
}
// Driver Code
public static void main(String[] args)
{
String S = "bbccdcbb";
longestPalindrome(S);
}
}
// This code is contributed by Princi Singh
Python3
# python3 implementation to find Longest
# Palindromic Subsequence consisting
# of two distinct characters only
# Function that prints the length of
# maximum required subsequence
def longestPalindrome(s):
# Calculate length of string
n = len(s)
pref = [[0 for i in range(n)] for j in range(26)]
pos = [[] for j in range(26)]
pref[ord(s[0]) - ord('a')][0] += 1
pos[ord(s[0]) - ord('a')].append(0)
# Store number of occurrences of each
# character and position of each
# character in string
for i in range(1,n):
for j in range(26):
pref[j][i] += pref[j][i - 1]
index = ord(s[i]) - ord('a')
pref[index][i] += 1
pos[index].append(i)
ans = 0
# Iterate all characters
for i in range(26):
# Calculate number of
# occurences of the
# current character
size = len(pos[i])
ans = max(ans, size)
# Iterate half of the
# number of positions
# of current character
for j in range(size // 2):
l = pos[i][j]
r = pos[i][size - j - 1] - 1
# Determine maximum length
# of a character between
# l and r position
for k in range(26):
sum = pref[k][r] - pref[k][l]
# Compute the maximum from all
ans = max(ans, 2 * (j + 1) + sum)
# Printing maximum length
print(ans)
# Driver Code
S = "bbccdcbb"
longestPalindrome(S)
# This code is contributed by shinjanpatra
C#
// C# implementation to find longest
// Palindromic Subsequence consisting
// of two distinct characters only
using System;
using System.Collections.Generic;
class GFG {
// Function that prints
// the length of maximum
// required subsequence
static void longestPalindrome(String s)
{
// Calculate length of String
int n = s.Length;
int[, ] pref = new int[26, n];
List<int>[] pos = new List<int>[ 26 ];
for (int i = 0; i < pos.Length; i++)
pos[i] = new List<int>();
pref[s[0] - 'a', 0]++;
pos[s[0] - 'a'].Add(0);
// Store number of occurrences of each
// character and position of each
// character in String
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++)
pref[j, i] += pref[j, i - 1];
int index = s[i] - 'a';
pref[index, i]++;
pos[index].Add(i);
}
int ans = 0;
// Iterate all characters
for (int i = 0; i < 26; i++) {
// Calculate number of
// occurences of the
// current character
int size = pos[i].Count;
ans = Math.Max(ans, size);
// Iterate half of the
// number of positions
// of current character
for (int j = 0; j < size / 2; j++) {
int l = pos[i][j];
int r = pos[i][size - j - 1] - 1;
// Determine maximum length
// of a character between
// l and r position
for (int k = 0; k < 26; k++) {
int sum = pref[k, r] - pref[k, l];
// Compute the maximum from all
ans = Math.Max(ans, 2 * (j + 1) + sum);
}
}
}
// Printing maximum length
Console.Write(ans + "\n");
}
// Driver Code
public static void Main(String[] args)
{
String S = "bbccdcbb";
longestPalindrome(S);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript implementation to find Longest
// Palindromic Subsequence consisting
// of two distinct characters only
// Function that prints the length of
// maximum required subsequence
function longestPalindrome(s)
{
// Calculate length of string
let n = s.length;
let pref = new Array(26);
for(let i = 0; i < 26; i++)
{
pref[i] = new Array(n).fill(0);
}
let pos = new Array(26);
for(let i = 0; i < 26; i++)
{
pos[i] = new Array();
}
pref[s.charCodeAt(0) - 'a'.charCodeAt(0)][0]++;
pos[s.charCodeAt(0) - 'a'.charCodeAt(0)].push(0);
// Store number of occurrences of each
// character and position of each
// character in string
for (let i = 1; i < n; i++) {
for (let j = 0; j < 26; j++)
pref[j][i] += pref[j][i - 1];
let index = s.charCodeAt(i) - 'a'.charCodeAt(0);
pref[index][i]++;
pos[index].push(i);
}
let ans = 0;
// Iterate all characters
for (let i = 0; i < 26; i++) {
// Calculate number of
// occurences of the
// current character
let size = pos[i].length;
ans = Math.max(ans, size);
// Iterate half of the
// number of positions
// of current character
for (let j = 0; j < (size / 2); j++) {
let l = pos[i][j];
let r = pos[i][size - j - 1] - 1;
// Determine maximum length
// of a character between
// l and r position
for (let k = 0; k < 26; k++) {
let sum = pref[k][r] - pref[k][l];
// Compute the maximum from all
ans = Math.max(ans, 2 * (j + 1) + sum);
}
}
}
// Printing maximum length
document.write(ans,"</br>");
}
// Driver Code
let S = "bbccdcbb";
longestPalindrome(S);
// This code is contributed by shinjanpatra
</script>
Producción:
7
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA