Dado un String s, cuente todas las substrings palindrómicas especiales de tamaño superior a 1. Una Substring se llama substring palindrómica especial si todos los caracteres en la substring son iguales o solo el carácter del medio es diferente por longitud impar. Ejemplo “aabaa” y “aaa” son substrings palindrómicas especiales y “abcba” no es una substring palindrómica especial.
Ejemplos:
Input : str = " abab" Output : 2 All Special Palindromic substring are: "aba", "bab" Input : str = "aabbb" Output : 4 All Special substring are: "aa", "bb", "bbb", "bb"
La solución simple es que simplemente generamos todas las substrings una por una y contamos cuántas substrings son substrings palindrómicas especiales. Esta solución toma O(n 3 ) tiempo.
Solución eficiente
Hay 2 casos:
Caso 1: Todas las substrings palindrómicas tienen el mismo carácter:
Podemos manejar este caso simplemente contando el mismo carácter continuo y usando la fórmula K*(K+1)/2 (número total de substrings posibles: Aquí K es el recuento del mismo carácter continuo).
Lets Str = "aaabba" Traverse string from left to right and Count of same char "aaabba" = 3, 2, 1 for "aaa" : total substring possible are 'aa' 'aa', 'aaa', 'a', 'a', 'a' : 3(3+1)/2 = 6 "bb" : 'b', 'b', 'bb' : 2(2+1)/2 = 3 'a' : 'a' : 1(1+1)/2 = 1
Caso 2:
podemos manejar este caso almacenando el recuento del mismo carácter en otra array temporal llamada «mismoCarácter[n]» de tamaño n. y elija cada carácter uno por uno y verifique que su carácter anterior y posterior sean iguales o no si son iguales, entonces hay min_entre ( mismoCarácter[previo], mismoCarácter[delantero]) substring posible.
Let's Str = "aabaaab" Count of smiler char from left to right : that we will store in Temporary array "sameChar" Str = " a a b a a a b " sameChar[] = 2 2 1 3 3 3 1 According to the problem statement middle character is different: so we have only left with char "b" at index :2 ( index from 0 to n-1) substring : "aabaaa" so only two substring are possible : "aabaa", "aba" that is min (smilerChar[index-1], smilerChar[index+1] ) that is 2.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to count special Palindromic substring
#include <bits/stdc++.h>
using namespace std;
// Function to count special Palindromic substring
int CountSpecialPalindrome(string str)
{
int n = str.length();
// store count of special Palindromic substring
int result = 0;
// it will store the count of continues same char
int sameChar[n] = { 0 };
int i = 0;
// traverse string character from left to right
while (i < n) {
// store same character count
int sameCharCount = 1;
int j = i + 1;
// count similar character
while (str[i] == str[j] && j < n)
sameCharCount++, j++;
// Case : 1
// so total number of substring that we can
// generate are : K *( K + 1 ) / 2
// here K is sameCharCount
result += (sameCharCount * (sameCharCount + 1) / 2);
// store current same char count in sameChar[]
// array
sameChar[i] = sameCharCount;
// increment i
i = j;
}
// Case 2: Count all odd length Special Palindromic
// substring
for (int j = 1; j < n; j++)
{
// if current character is equal to previous
// one then we assign Previous same character
// count to current one
if (str[j] == str[j - 1])
sameChar[j] = sameChar[j - 1];
// case 2: odd length
if (j > 0 && j < (n - 1) &&
(str[j - 1] == str[j + 1] &&
str[j] != str[j - 1]))
result += min(sameChar[j - 1],
sameChar[j + 1]);
}
// subtract all single length substring
return result - n;
}
// driver program to test above fun
int main()
{
string str = "abccba";
cout << CountSpecialPalindrome(str) << endl;
return 0;
}
Java
// Java program to count special
// Palindromic substring
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG
{
// Function to count special
// Palindromic substring
public static int CountSpecialPalindrome(String str)
{
int n = str.length();
// store count of special
// Palindromic substring
int result = 0;
// it will store the count
// of continues same char
int[] sameChar = new int[n];
for(int v = 0; v < n; v++)
sameChar[v] = 0;
int i = 0;
// traverse string character
// from left to right
while (i < n)
{
// store same character count
int sameCharCount = 1;
int j = i + 1;
// count similar character
while (j < n &&
str.charAt(i) == str.charAt(j))
{
sameCharCount++;
j++;
}
// Case : 1
// so total number of
// substring that we can
// generate are : K *( K + 1 ) / 2
// here K is sameCharCount
result += (sameCharCount *
(sameCharCount + 1) / 2);
// store current same char
// count in sameChar[] array
sameChar[i] = sameCharCount;
// increment i
i = j;
}
// Case 2: Count all odd length
// Special Palindromic
// substring
for (int j = 1; j < n; j++)
{
// if current character is
// equal to previous one
// then we assign Previous
// same character count to
// current one
if (str.charAt(j) == str.charAt(j - 1))
sameChar[j] = sameChar[j - 1];
// case 2: odd length
if (j > 0 && j < (n - 1) &&
(str.charAt(j - 1) == str.charAt(j + 1) &&
str.charAt(j) != str.charAt(j - 1)))
result += Math.min(sameChar[j - 1],
sameChar[j + 1]);
}
// subtract all single
// length substring
return result - n;
}
// Driver code
public static void main(String args[])
{
String str = "abccba";
System.out.print(CountSpecialPalindrome(str));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
Python3
# Python3 program to count special # Palindromic substring # Function to count special # Palindromic substring def CountSpecialPalindrome(str): n = len(str); # store count of special # Palindromic substring result = 0; # it will store the count # of continues same char sameChar=[0] * n; i = 0; # traverse string character # from left to right while (i < n): # store same character count sameCharCount = 1; j = i + 1; # count smiler character while (j < n): if(str[i] != str[j]): break; sameCharCount += 1; j += 1; # Case : 1 # so total number of substring # that we can generate are : # K *( K + 1 ) / 2 # here K is sameCharCount result += int(sameCharCount * (sameCharCount + 1) / 2); # store current same char # count in sameChar[] array sameChar[i] = sameCharCount; # increment i i = j; # Case 2: Count all odd length # Special Palindromic substring for j in range(1, n): # if current character is equal # to previous one then we assign # Previous same character count # to current one if (str[j] == str[j - 1]): sameChar[j] = sameChar[j - 1]; # case 2: odd length if (j > 0 and j < (n - 1) and (str[j - 1] == str[j + 1] and str[j] != str[j - 1])): result += (sameChar[j - 1] if(sameChar[j - 1] < sameChar[j + 1]) else sameChar[j + 1]); # subtract all single # length substring return result-n; # Driver Code str = "abccba"; print(CountSpecialPalindrome(str)); # This code is contributed by mits.
C#
// C# program to count special
// Palindromic substring
using System;
class GFG
{
// Function to count special
// Palindromic substring
public static int CountSpecialPalindrome(String str)
{
int n = str.Length;
// store count of special
// Palindromic substring
int result = 0;
// it will store the count
// of continues same char
int[] sameChar = new int[n];
for(int v = 0; v < n; v++)
sameChar[v] = 0;
int i = 0;
// traverse string character
// from left to right
while (i < n)
{
// store same character count
int sameCharCount = 1;
int j = i + 1;
// count smiler character
while (j < n &&
str[i] == str[j])
{
sameCharCount++;
j++;
}
// Case : 1
// so total number of
// substring that we can
// generate are : K *( K + 1 ) / 2
// here K is sameCharCount
result += (sameCharCount *
(sameCharCount + 1) / 2);
// store current same char
// count in sameChar[] array
sameChar[i] = sameCharCount;
// increment i
i = j;
}
// Case 2: Count all odd length
// Special Palindromic
// substring
for (int j = 1; j < n; j++)
{
// if current character is
// equal to previous one
// then we assign Previous
// same character count to
// current one
if (str[j] == str[j - 1])
sameChar[j] = sameChar[j - 1];
// case 2: odd length
if (j > 0 && j < (n - 1) &&
(str[j - 1] == str[j + 1] &&
str[j] != str[j - 1]))
result += Math.Min(sameChar[j - 1],
sameChar[j + 1]);
}
// subtract all single
// length substring
return result - n;
}
// Driver code
public static void Main()
{
String str = "abccba";
Console.Write(CountSpecialPalindrome(str));
}
}
// This code is contributed by mits.
PHP
<?php
// PHP program to count special
// Palindromic substring
// Function to count special
// Palindromic substring
function CountSpecialPalindrome($str)
{
$n = strlen($str);
// store count of special
// Palindromic substring
$result = 0;
// it will store the count
// of continues same char
$sameChar=array_fill(0, $n, 0);
$i = 0;
// traverse string character
// from left to right
while ($i < $n)
{
// store same character count
$sameCharCount = 1;
$j = $i + 1;
// count smiler character
while ($j < $n)
{
if($str[$i] != $str[$j])
break;
$sameCharCount++;
$j++;
}
// Case : 1
// so total number of substring
// that we can generate are :
// K *( K + 1 ) / 2
// here K is sameCharCount
$result += (int)($sameCharCount *
($sameCharCount + 1) / 2);
// store current same char
// count in sameChar[] array
$sameChar[$i] = $sameCharCount;
// increment i
$i = $j;
}
// Case 2: Count all odd length
// Special Palindromic substring
for ($j = 1; $j < $n; $j++)
{
// if current character is equal
// to previous one then we assign
// Previous same character count
// to current one
if ($str[$j] == $str[$j - 1])
$sameChar[$j] = $sameChar[$j - 1];
// case 2: odd length
if ($j > 0 && $j < ($n - 1) &&
($str[$j - 1] == $str[$j + 1] &&
$str[$j] != $str[$j - 1]))
$result += $sameChar[$j - 1] <
$sameChar[$j + 1] ?
$sameChar[$j - 1] :
$sameChar[$j + 1];
}
// subtract all single
// length substring
return $result - $n;
}
// Driver Code
$str = "abccba";
echo CountSpecialPalindrome($str);
// This code is contributed by mits.
?>
Javascript
<script>
// JavaScript program to count special Palindromic substring
// Function to count special Palindromic substring
function CountSpecialPalindrome(str) {
var n = str.length;
// store count of special Palindromic substring
var result = 0;
// it will store the count of continues same char
var sameChar = [...Array(n)];
var i = 0;
// traverse string character from left to right
while (i < n) {
// store same character count
var sameCharCount = 1;
var j = i + 1;
// count smiler character
while (str[i] == str[j] && j < n) sameCharCount++, j++;
// Case : 1
// so total number of substring that we can
// generate are : K *( K + 1 ) / 2
// here K is sameCharCount
result += (sameCharCount * (sameCharCount + 1)) / 2;
// store current same char count in sameChar[]
// array
sameChar[i] = sameCharCount;
// increment i
i = j;
}
// Case 2: Count all odd length Special Palindromic
// substring
for (var j = 1; j < n; j++) {
// if current character is equal to previous
// one then we assign Previous same character
// count to current one
if (str[j] == str[j - 1]) sameChar[j] = sameChar[j - 1];
// case 2: odd length
if (
j > 0 &&
j < n - 1 &&
str[j - 1] == str[j + 1] &&
str[j] != str[j - 1]
)
result += Math.min(sameChar[j - 1], sameChar[j + 1]);
}
// subtract all single length substring
return result - n;
}
// driver program to test above fun
var str = "abccba";
document.write(CountSpecialPalindrome(str) + "<br>");
</script>
Producción :
1
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por Nishant_Singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA