Dada una string S de longitud n y un entero positivo k. La tarea es encontrar el número de subsecuencias palindrómicas de longitud k donde k <= 3.
Ejemplos:
Input : s = "aabab", k = 2 Output : 4
Input : s = "aaa", k = 3 Output : 1
Para k = 1 , podemos decir fácilmente que el número de caracteres en la string será la respuesta.
Para k = 2 , podemos hacer fácilmente pares de los mismos caracteres, por lo que debemos mantener el recuento de cada carácter en la string y luego calcular
sum = 0 for character 'a' to 'z' cnt = count(character) sum = sum + cnt*(cnt-1)/2 sum is the answer.
Ahora, a medida que aumenta k, se vuelve difícil de encontrar. ¿Cómo encontrar la respuesta para k = 3 ? Entonces, la idea es ver que los palíndromos de longitud 3 tendrán el formato TZT, por lo que debemos mantener dos arrays, una para calcular la suma del prefijo de cada carácter y otra para calcular la suma del sufijo de cada carácter en la string.
La suma del prefijo para un carácter T en el índice i es L[T][i], es decir, el número de veces que T ha ocurrido en el rango [0, i](índices).
La suma de sufijos para un carácter T en el índice i es R[T][i] ha ocurrido en el rango [i, n – 1](índices).
Ambas arrays serán 26*n y se pueden precalcular ambas arrays en complejidad O(26*n) donde n es la longitud de la string.
Ahora, ¿cómo calcular la subsecuencia? Piense en esto:
para un índice, supongo que un carácter X aparece n1 veces en el rango [0, i – 1] y n2 veces en el rango [i + 1, n – 1], entonces la respuesta para este carácter será n1 * n2, es decir, L[X][i-1] * R[X][i + 1], esto dará el recuento de subsecuencias del formato Xs[i]-X donde s[i] es el carácter en i-th índice. Así que para cada índice i tendrás que contar el producto de
L[X][i-1] * R[X][i+1],
where i is the range [1, n-2] and
X will be from 'a' to 'z'
A continuación se muestra la implementación de este enfoque:
C++
// CPP program to count number of subsequences of
// given length.
#include <bits/stdc++.h>
#define MAX 100
#define MAX_CHAR 26
using namespace std;
// Precompute the prefix and suffix array.
void precompute(string s, int n, int l[][MAX],
int r[][MAX])
{
l[s[0] - 'a'][0] = 1;
// Precompute the prefix 2D array
for (int i = 1; i < n; i++) {
for (int j = 0; j < MAX_CHAR; j++)
l[j][i] += l[j][i - 1];
l[s[i] - 'a'][i]++;
}
r[s[n - 1] - 'a'][n - 1] = 1;
// Precompute the Suffix 2D array.
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < MAX_CHAR; j++)
r[j][i] += r[j][i + 1];
r[s[i] - 'a'][i]++;
}
}
// Find the number of palindromic subsequence of
// length k
int countPalindromes(int k, int n, int l[][MAX],
int r[][MAX])
{
int ans = 0;
// If k is 1.
if (k == 1) {
for (int i = 0; i < MAX_CHAR; i++)
ans += l[i][n - 1];
return ans;
}
// If k is 2
if (k == 2) {
// Adding all the products of prefix array
for (int i = 0; i < MAX_CHAR; i++)
ans += ((l[i][n - 1] * (l[i][n - 1] - 1)) / 2);
return ans;
}
// For k greater than 2. Adding all the products
// of value of prefix and suffix array.
for (int i = 1; i < n - 1; i++)
for (int j = 0; j < MAX_CHAR; j++)
ans += l[j][i - 1] * r[j][i + 1];
return ans;
}
// Driven Program
int main()
{
string s = "aabab";
int k = 2;
int n = s.length();
int l[MAX_CHAR][MAX] = { 0 }, r[MAX_CHAR][MAX] = { 0 };
precompute(s, n, l, r);
cout << countPalindromes(k, n, l, r) << endl;
return 0;
}
Java
// Java program to count number of subsequences of
// given length.
class GFG
{
static final int MAX=100;
static final int MAX_CHAR=26;
// Precompute the prefix and suffix array.
static void precompute(String s, int n, int l[][],
int r[][])
{
l[s.charAt(0) - 'a'][0] = 1;
// Precompute the prefix 2D array
for (int i = 1; i < n; i++) {
for (int j = 0; j < MAX_CHAR; j++)
l[j][i] += l[j][i - 1];
l[s.charAt(i) - 'a'][i]++;
}
r[s.charAt(n - 1) - 'a'][n - 1] = 1;
// Precompute the Suffix 2D array.
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < MAX_CHAR; j++)
r[j][i] += r[j][i + 1];
r[s.charAt(i) - 'a'][i]++;
}
}
// Find the number of palindromic subsequence of
// length k
static int countPalindromes(int k, int n, int l[][],
int r[][])
{
int ans = 0;
// If k is 1.
if (k == 1) {
for (int i = 0; i < MAX_CHAR; i++)
ans += l[i][n - 1];
return ans;
}
// If k is 2
if (k == 2) {
// Adding all the products of prefix array
for (int i = 0; i < MAX_CHAR; i++)
ans += ((l[i][n - 1] * (l[i][n - 1] - 1)) / 2);
return ans;
}
// For k greater than 2. Adding all the products
// of value of prefix and suffix array.
for (int i = 1; i < n - 1; i++)
for (int j = 0; j < MAX_CHAR; j++)
ans += l[j][i - 1] * r[j][i + 1];
return ans;
}
// Driver code
public static void main (String[] args)
{
String s = "aabab";
int k = 2;
int n = s.length();
int l[][]=new int[MAX_CHAR][MAX];
int r[][]=new int[MAX_CHAR][MAX];
precompute(s, n, l, r);
System.out.println(countPalindromes(k, n, l, r));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to count number of
# subsequences of given length.
MAX = 100
MAX_CHAR = 26
# Precompute the prefix and suffix array.
def precompute(s, n, l, r):
l[ord(s[0]) - ord('a')][0] = 1
# Precompute the prefix 2D array
for i in range(1, n):
for j in range(MAX_CHAR):
l[j][i] += l[j][i - 1]
l[ord(s[i]) - ord('a')][i] += 1
r[ord(s[n - 1]) - ord('a')][n - 1] = 1
# Precompute the Suffix 2D array.
k = n - 2
while(k >= 0):
for j in range(MAX_CHAR):
r[j][k] += r[j][k + 1]
r[ord(s[k]) - ord('a')][k] += 1
k -= 1
# Find the number of palindromic
# subsequence of length k
def countPalindromes(k, n, l, r):
ans = 0
# If k is 1.
if (k == 1):
for i in range(MAX_CHAR):
ans += l[i][n - 1]
return ans
# If k is 2
if (k == 2):
# Adding all the products of
# prefix array
for i in range(MAX_CHAR):
ans += ((l[i][n - 1] * (l[i][n - 1] - 1)) / 2)
return ans
# For k greater than 2. Adding all
# the products of value of prefix
# and suffix array.
for i in range(1, n - 1):
for j in range(MAX_CHAR):
ans += l[j][i - 1] * r[j][i + 1]
return ans
# Driven Program
s = "aabab"
k = 2
n = len(s)
l = [[0 for x in range(MAX)] for y in range(MAX_CHAR)]
r = [[0 for x in range(MAX)] for y in range(MAX_CHAR)]
precompute(s, n, l, r)
print (countPalindromes(k, n, l, r))
# This code is written by Sachin Bisht
C#
// C# program to count number of
// subsequences of given length.
using System;
class GFG {
static int MAX=100;
static int MAX_CHAR=26;
// Precompute the prefix
// and suffix array.
static void precompute(string s, int n,
int [,]l, int [,]r)
{
l[s[0] - 'a',0] = 1;
// Precompute the
// prefix 2D array
for (int i = 1; i < n; i++)
{
for (int j = 0; j < MAX_CHAR; j++)
l[j, i] += l[j,i - 1];
l[s[i] - 'a',i]++;
}
r[s[n - 1] - 'a',n - 1] = 1;
// Precompute the Suffix 2D array.
for (int i = n - 2; i >= 0; i--)
{
for (int j = 0; j < MAX_CHAR; j++)
r[j, i] += r[j,i + 1];
r[s[i] - 'a',i]++;
}
}
// Find the number of palindromic
// subsequence of length k
static int countPalindromes(int k, int n,
int [,]l, int [,]r)
{
int ans = 0;
// If k is 1.
if (k == 1)
{
for (int i = 0; i < MAX_CHAR; i++)
ans += l[i,n - 1];
return ans;
}
// If k is 2
if (k == 2) {
// Adding all the products
// of prefix array
for (int i = 0; i < MAX_CHAR; i++)
ans += ((l[i,n - 1] *
(l[i,n - 1] - 1)) / 2);
return ans;
}
// For k greater than 2.
// Adding all the products
// of value of prefix and
// suffix array.
for (int i = 1; i < n - 1; i++)
for (int j = 0; j < MAX_CHAR; j++)
ans += l[j,i - 1] * r[j, i + 1];
return ans;
}
// Driver code
public static void Main ()
{
string s = "aabab";
int k = 2;
int n = s.Length;
int [,]l=new int[MAX_CHAR,MAX];
int [,]r=new int[MAX_CHAR,MAX];
precompute(s, n, l, r);
Console.Write(countPalindromes(k, n, l, r));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to count number of
// subsequences of given length.
$MAX = 100;
$MAX_CHAR = 26;
// Precompute the prefix and suffix array.
function precompute($s, $n, &$l, &$r)
{
global $MAX, $MAX_CHAR;
$l[ord($s[0]) - ord('a')][0] = 1;
// Precompute the prefix 2D array
for ($i = 1; $i < $n; $i++)
{
for ($j = 0; $j < $MAX_CHAR; $j++)
$l[$j][$i] += $l[$j][$i - 1];
$l[ord($s[$i]) - ord('a')][$i]++;
}
$r[ord($s[$n - 1]) - ord('a')][$n - 1] = 1;
// Precompute the Suffix 2D array.
for ($i = $n - 2; $i >= 0; $i--)
{
for ($j = 0; $j < $MAX_CHAR; $j++)
$r[$j][$i] += $r[$j][$i + 1];
$r[ord($s[$i]) - ord('a')][$i]++;
}
}
// Find the number of palindromic
// subsequence of length k
function countPalindromes($k, $n, &$l, &$r)
{
global $MAX, $MAX_CHAR;
$ans = 0;
// If k is 1.
if ($k == 1)
{
for ($i = 0; $i < $MAX_CHAR; $i++)
$ans += $l[$i][$n - 1];
return $ans;
}
// If k is 2
if ($k == 2)
{
// Adding all the products of
// prefix array
for ($i = 0; $i < $MAX_CHAR; $i++)
$ans += (($l[$i][$n - 1] *
($l[$i][$n - 1] - 1)) / 2);
return $ans;
}
// For k greater than 2. Adding all
// the products of value of prefix
// and suffix array.
for ($i = 1; $i < $n - 1; $i++)
for ($j = 0; $j < $MAX_CHAR; $j++)
$ans += $l[$j][$i - 1] *
$r[$j][$i + 1];
return $ans;
}
// Driver Code
$s = "aabab";
$k = 2;
$n = strlen($s);
$l = array_fill(0, $MAX_CHAR,
array_fill(0, $MAX, NULL));
$r = array_fill(0, $MAX_CHAR,
array_fill(0, $MAX, NULL));
precompute($s, $n, $l, $r);
echo countPalindromes($k, $n, $l, $r) . "\n";
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to count number of subsequences of
// given length.
let MAX=100;
let MAX_CHAR=26;
// Precompute the prefix and suffix array.
function precompute(s,n,l,r)
{
l[s[0].charCodeAt(0) - 'a'.charCodeAt(0)][0] = 1;
// Precompute the prefix 2D array
for (let i = 1; i < n; i++) {
for (let j = 0; j < MAX_CHAR; j++)
l[j][i] += l[j][i - 1];
l[s[i].charCodeAt(0) - 'a'.charCodeAt(0)][i]++;
}
r[s[n-1].charCodeAt(0) - 'a'.charCodeAt(0)][n - 1] = 1;
// Precompute the Suffix 2D array.
for (let i = n - 2; i >= 0; i--) {
for (let j = 0; j < MAX_CHAR; j++)
r[j][i] += r[j][i + 1];
r[s[i].charCodeAt(0) - 'a'.charCodeAt(0)][i]++;
}
}
// Find the number of palindromic subsequence of
// length k
function countPalindromes(k,n,l,r)
{
let ans = 0;
// If k is 1.
if (k == 1) {
for (let i = 0; i < MAX_CHAR; i++)
ans += l[i][n - 1];
return ans;
}
// If k is 2
if (k == 2) {
// Adding all the products of prefix array
for (let i = 0; i < MAX_CHAR; i++)
ans += ((l[i][n - 1] * (l[i][n - 1] - 1)) / 2);
return ans;
}
// For k greater than 2. Adding all the products
// of value of prefix and suffix array.
for (let i = 1; i < n - 1; i++)
for (let j = 0; j < MAX_CHAR; j++)
ans += l[j][i - 1] * r[j][i + 1];
return ans;
}
// Driver code
let s = "aabab";
let k = 2;
let n = s.length;
let l=new Array(MAX_CHAR);
let r= new Array(MAX_CHAR);
for(let i=0;i<MAX_CHAR;i++)
{
l[i]=new Array(MAX);
r[i]=new Array(MAX);
for(let j=0;j<MAX;j++)
{
l[i][j]=0;
r[i][j]=0;
}
}
precompute(s, n, l, r);
document.write(countPalindromes(k, n, l, r));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
4