Dada una string S. La tarea es contar los pares no superpuestos de substrings palindrómicas S1 y S2 de modo que las strings sean S1[L1…R1] y S2[L2…R2] donde 0 ≤ L1 ≤ R1 < L2 ≤ R2 < N . La tarea es contar el número de pares de substrings palindrómicas que no se superponen.
Ejemplos:
Entrada: s = “aaa”
Salida: 5
Todos los pares posibles son (s[0], s[1]), (s[0], s[2]),
(s[0], s[1, 2] ), (s[1], s[2]) y (s[0, 1], s[2])
Entrada: s = “abacaba”
Salida: 36
Enfoque: podemos usar la programación dinámica para resolver el problema anterior. Inicialmente podemos crear la tabla DP que almacena si la substring [i….j] es palíndromo o no. Mantenemos un booleano dp[n][n] que se llena de forma ascendente. El valor de dp[i][j] es verdadero si la substring es un palíndromo; de lo contrario, es falso. Para calcular dp[i][j], primero verificamos el valor de dp[i+1][j-1] , si el valor es verdadero y s[i] es igual a s[j] , entonces hacemos dp [i][j] cierto. De lo contrario, el valor de dp[i][j] se hace falso. A partir de entonces, se pueden seguir los siguientes pasos para obtener el número de pares.
- Cree una array left[] , donde left[i] almacena el recuento del número de palíndromos a la izquierda en el índice i, incluido i.
- Cree una array right[] , donde right[i] almacena el recuento del número de palíndromos a la derecha en el índice i, incluido i.
- Iterar de 0 a length-1 y agregar left[i]*right[i+1] . La suma de la misma para cada índice será el número requerido de pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100
// Pre-processing function
void pre_process(bool dp[N][N], string s)
{
// Get the size of the string
int n = s.size();
// Initially mark every
// position as false
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
dp[i][j] = false;
}
// For the length
for (int j = 1; j <= n; j++) {
// Iterate for every index with
// length j
for (int i = 0; i <= n - j; i++) {
// If the length is less than 2
if (j <= 2) {
// If characters are equal
if (s[i] == s[i + j - 1])
dp[i][i + j - 1] = true;
}
// Check for equal
else if (s[i] == s[i + j - 1])
dp[i][i + j - 1] = dp[i + 1][i + j - 2];
}
}
}
// Function to return the number of pairs
int countPairs(string s)
{
// Create the dp table initially
bool dp[N][N];
pre_process(dp, s);
int n = s.length();
// Declare the left array
int left[n];
memset(left, 0, sizeof left);
// Declare the right array
int right[n];
memset(right, 0, sizeof right);
// Initially left[0] is 1
left[0] = 1;
// Count the number of palindrome
// pairs to the left
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (dp[j][i] == 1)
left[i]++;
}
}
// Initially right most as 1
right[n - 1] = 1;
// Count the number of palindrome
// pairs to the right
for (int i = n - 2; i >= 0; i--) {
right[i] = right[i + 1];
for (int j = n - 1; j >= i; j--) {
if (dp[i][j] == 1)
right[i]++;
}
}
int ans = 0;
// Count the number of pairs
for (int i = 0; i < n - 1; i++)
ans += left[i] * right[i + 1];
return ans;
}
// Driver code
int main()
{
string s = "abacaba";
cout << countPairs(s);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int N = 100;
// Pre-processing function
static void pre_process(boolean dp[][], char[] s)
{
// Get the size of the string
int n = s.length;
// Initially mark every
// position as false
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
dp[i][j] = false;
}
}
// For the length
for (int j = 1; j <= n; j++)
{
// Iterate for every index with
// length j
for (int i = 0; i <= n - j; i++)
{
// If the length is less than 2
if (j <= 2)
{
// If characters are equal
if (s[i] == s[i + j - 1])
{
dp[i][i + j - 1] = true;
}
}
// Check for equal
else if (s[i] == s[i + j - 1])
{
dp[i][i + j - 1] = dp[i + 1][i + j - 2];
}
}
}
}
// Function to return the number of pairs
static int countPairs(String s)
{
// Create the dp table initially
boolean dp[][] = new boolean[N][N];
pre_process(dp, s.toCharArray());
int n = s.length();
// Declare the left array
int left[] = new int[n];
// Declare the right array
int right[] = new int[n];
// Initially left[0] is 1
left[0] = 1;
// Count the number of palindrome
// pairs to the left
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
if (dp[j][i] == true)
{
left[i]++;
}
}
}
// Initially right most as 1
right[n - 1] = 1;
// Count the number of palindrome
// pairs to the right
for (int i = n - 2; i >= 0; i--)
{
right[i] = right[i + 1];
for (int j = n - 1; j >= i; j--)
{
if (dp[i][j] == true)
{
right[i]++;
}
}
}
int ans = 0;
// Count the number of pairs
for (int i = 0; i < n - 1; i++)
{
ans += left[i] * right[i + 1];
}
return ans;
}
// Driver code
public static void main(String[] args)
{
String s = "abacaba";
System.out.println(countPairs(s));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the approach N = 100 # Pre-processing function def pre_process(dp, s): # Get the size of the string n = len(s) # Initially mark every # position as false for i in range(n): for j in range(n): dp[i][j] = False # For the length for j in range(1, n + 1): # Iterate for every index with # length j for i in range(n - j + 1): # If the length is less than 2 if (j <= 2): # If characters are equal if (s[i] == s[i + j - 1]): dp[i][i + j - 1] = True # Check for equal elif (s[i] == s[i + j - 1]): dp[i][i + j - 1] = dp[i + 1][i + j - 2] # Function to return the number of pairs def countPairs(s): # Create the dp table initially dp = [[False for i in range(N)] for j in range(N)] pre_process(dp, s) n = len(s) # Declare the left array left = [0 for i in range(n)] # Declare the right array right = [0 for i in range(n)] # Initially left[0] is 1 left[0] = 1 # Count the number of palindrome # pairs to the left for i in range(1, n): for j in range(i + 1): if (dp[j][i] == 1): left[i] += 1 # Initially right most as 1 right[n - 1] = 1 # Count the number of palindrome # pairs to the right for i in range(n - 2, -1, -1): right[i] = right[i + 1] for j in range(n - 1, i - 1, -1): if (dp[i][j] == 1): right[i] += 1 ans = 0 # Count the number of pairs for i in range(n - 1): ans += left[i] * right[i + 1] return ans # Driver code s = "abacaba" print(countPairs(s)) # This code is contributed by mohit kumar
PHP
<?php
// PHP implementation of the approach
$N = 100;
// Pre-processing function
function pre_process($dp, $s)
{
// Get the size of the string
$n = strlen($s);
// Initially mark every
// position as false
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
$dp[$i][$j] = false;
}
// For the length
for ($j = 1; $j <= $n; $j++)
{
// Iterate for every index with
// length j
for ($i = 0; $i <= $n - $j; $i++)
{
// If the length is less than 2
if ($j <= 2)
{
// If characters are equal
if ($s[$i] == $s[$i + $j - 1])
$dp[$i][$i + $j - 1] = true;
}
// Check for equal
else if ($s[$i] == $s[$i + $j - 1])
$dp[$i][$i + $j - 1] = $dp[$i + 1][$i + $j - 2];
}
}
return $dp;
}
// Function to return the number of pairs
function countPairs($s)
{
// Create the dp table initially
$dp = array(array());
$dp = pre_process($dp, $s);
$n = strlen($s);
// Declare the left array
$left = array_fill(0, $n, 0);
// Declare the right array
$right = array_fill(0, $n, 0);
// Initially left[0] is 1
$left[0] = 1;
// Count the number of palindrome
// pairs to the left
for ($i = 1; $i < $n; $i++)
{
for ($j = 0; $j <= $i; $j++)
{
if ($dp[$j][$i] == 1)
$left[$i]++;
}
}
// Initially right most as 1
$right[$n - 1] = 1;
// Count the number of palindrome
// pairs to the right
for ($i = $n - 2; $i >= 0; $i--)
{
$right[$i] = $right[$i + 1];
for ($j = $n - 1; $j >= $i; $j--)
{
if ($dp[$i][$j] == 1)
$right[$i]++;
}
}
$ans = 0;
// Count the number of pairs
for ($i = 0; $i < $n - 1; $i++)
$ans += $left[$i] * $right[$i + 1];
return $ans;
}
// Driver code
$s = "abacaba";
echo countPairs($s);
// This code is contributed by Ryuga
?>
C#
// C# implementation of the approach
using System;
class GFG
{
static int N = 100;
// Pre-processing function
static void pre_process(bool [,]dp, char[] s)
{
// Get the size of the string
int n = s.Length;
// Initially mark every
// position as false
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
dp[i,j] = false;
}
}
// For the length
for (int j = 1; j <= n; j++)
{
// Iterate for every index with
// length j
for (int i = 0; i <= n - j; i++)
{
// If the length is less than 2
if (j <= 2)
{
// If characters are equal
if (s[i] == s[i + j - 1])
{
dp[i,i + j - 1] = true;
}
}
// Check for equal
else if (s[i] == s[i + j - 1])
{
dp[i,i + j - 1] = dp[i + 1,i + j - 2];
}
}
}
}
// Function to return the number of pairs
static int countPairs(String s)
{
// Create the dp table initially
bool [,]dp = new bool[N,N];
pre_process(dp, s.ToCharArray());
int n = s.Length;
// Declare the left array
int []left = new int[n];
// Declare the right array
int []right = new int[n];
// Initially left[0] is 1
left[0] = 1;
// Count the number of palindrome
// pairs to the left
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
if (dp[j,i] == true)
{
left[i]++;
}
}
}
// Initially right most as 1
right[n - 1] = 1;
// Count the number of palindrome
// pairs to the right
for (int i = n - 2; i >= 0; i--)
{
right[i] = right[i + 1];
for (int j = n - 1; j >= i; j--)
{
if (dp[i,j] == true)
{
right[i]++;
}
}
}
int ans = 0;
// Count the number of pairs
for (int i = 0; i < n - 1; i++)
{
ans += left[i] * right[i + 1];
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
String s = "abacaba";
Console.Write(countPairs(s));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// javascript implementation of the approach
var N = 100;
// Pre-processing function
function pre_process( dp, s) {
// Get the size of the string
var n = s.length;
// Initially mark every
// position as false
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
dp[i][j] = false;
}
}
// For the length
for (j = 1; j <= n; j++) {
// Iterate for every index with
// length j
for (i = 0; i <= n - j; i++) {
// If the length is less than 2
if (j <= 2) {
// If characters are equal
if (s[i] == s[i + j - 1]) {
dp[i][i + j - 1] = true;
}
}
// Check for equal
else if (s[i] == s[i + j - 1]) {
dp[i][i + j - 1] = dp[i + 1][i + j - 2];
}
}
}
}
// Function to return the number of pairs
function countPairs(s) {
// Create the dp table initially
var dp = Array(N).fill().map(()=>Array(N).fill(false));
pre_process(dp, s);
var n = s.length;
// Declare the left array
var left = Array(n).fill(0);
// Declare the right array
var right = Array(n).fill(0);
// Initially left[0] is 1
left[0] = 1;
// Count the number of palindrome
// pairs to the left
for (i = 1; i < n; i++) {
for (j = 0; j <= i; j++) {
if (dp[j][i] == true) {
left[i]++;
}
}
}
// Initially right most as 1
right[n - 1] = 1;
// Count the number of palindrome
// pairs to the right
for (i = n - 2; i >= 0; i--) {
right[i] = right[i + 1];
for (j = n - 1; j >= i; j--) {
if (dp[i][j] == true) {
right[i]++;
}
}
}
var ans = 0;
// Count the number of pairs
for (i = 0; i < n - 1; i++) {
ans += left[i] * right[i + 1];
}
return ans;
}
// Driver code
var s = "abacaba";
document.write(countPairs(s));
// This code is contributed by todaysgaurav
</script>
Producción:
36
Complejidad de tiempo: O (N * N), ya que estamos usando bucles anidados para atravesar N * N veces. Donde N es la longitud de la string.
Espacio auxiliar: O(N*N), ya que estamos usando espacio adicional para la array dp.