Dado que la string str consta solo de letras minúsculas y un número entero K , la tarea es contar el número de substrings de tamaño K de modo que cualquier permutación de la substring sea un palíndromo.
Ejemplos:
Entrada: str = “abbaca”, K = 3
Salida: 3
Explicación:
Las substrings de tamaño 3 cuya permutación es palíndromo son {“abb”, “bba”, “aca”}.Entrada: str = “aaaa”, K = 1
Salida: 4
Explicación:
Las substrings de tamaño 1 cuya permutación es palíndromo son {‘a’, ‘a’, ‘a’, ‘a’}.
Enfoque ingenuo: una solución ingenua es ejecutar un bucle doble para generar todas las substrings de tamaño K . Para cada substring formada, encuentre la frecuencia de cada carácter de la substring. Si como máximo un carácter tiene una frecuencia impar, entonces una de sus permutaciones será un palíndromo . Incremente el recuento de la substring actual e imprima el recuento final después de todas las operaciones.
Complejidad de tiempo: O(N*K)
Enfoque eficiente: este problema se puede resolver de manera eficiente mediante el uso de la técnica de deslizamiento de ventanas y el uso de una array de frecuencias de tamaño 26 . A continuación se muestran los pasos:
- Almacene la frecuencia de los primeros K elementos de la string dada en una array de frecuencia (por ejemplo , freq[] ).
- Usando una array de frecuencias, verifique el conteo de elementos que tienen una frecuencia impar. Si es menor que 2 , entonces el incremento de la cuenta de permutación palindrómica.
- Ahora, deslice linealmente la ventana hacia adelante hasta que llegue al final.
- En cada iteración, reduzca el conteo del primer elemento de la ventana en 1 y aumente el conteo del siguiente elemento de la ventana en 1 y nuevamente verifique el conteo de elementos en una array de frecuencia que tiene una frecuencia impar. Si es menor que 2 , aumente el recuento de la permutación palindrómica.
- Repita el paso anterior hasta que lleguemos al final de la string e imprimamos la cuenta de permutación palindrómica.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// To store the frequency array
vector<int> freq(26);
// Function to check palindromic of
// of any substring using frequency array
bool checkPalindrome()
{
// Initialise the odd count
int oddCnt = 0;
// Traversing frequency array to
// compute the count of characters
// having odd frequency
for (auto x : freq) {
if (x % 2 == 1)
oddCnt++;
}
// Returns true if odd count is atmost 1
return oddCnt <= 1;
}
// Function to count the total number
// substring whose any permutations
// are palindromic
int countPalindromePermutation(
string s, int k)
{
// Computing the frequency of
// first K character of the string
for (int i = 0; i < k; i++) {
freq[s[i] - 97]++;
}
// To store the count of
// palindromic permutations
int ans = 0;
// Checking for the current window
// if it has any palindromic
// permutation
if (checkPalindrome()) {
ans++;
}
// Start and end point of window
int i = 0, j = k;
while (j < s.size()) {
// Sliding window by 1
// Decrementing count of first
// element of the window
freq[s[i++] - 97]--;
// Incrementing count of next
// element of the window
freq[s[j++] - 97]++;
// Checking current window
// character frequency count
if (checkPalindrome()) {
ans++;
}
}
// Return the final count
return ans;
}
// Driver Code
int main()
{
// Given string str
string str = "abbaca";
// Window of size K
int K = 3;
// Function Call
cout << countPalindromePermutation(str, K)
<< endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// To store the frequency array
static int []freq = new int[26];
// Function to check palindromic of
// of any subString using frequency array
static boolean checkPalindrome()
{
// Initialise the odd count
int oddCnt = 0;
// Traversing frequency array to
// compute the count of characters
// having odd frequency
for(int x : freq)
{
if (x % 2 == 1)
oddCnt++;
}
// Returns true if odd count
// is atmost 1
return oddCnt <= 1;
}
// Function to count the total number
// subString whose any permutations
// are palindromic
static int countPalindromePermutation(char []s,
int k)
{
// Computing the frequency of
// first K character of the String
for(int i = 0; i < k; i++)
{
freq[s[i] - 97]++;
}
// To store the count of
// palindromic permutations
int ans = 0;
// Checking for the current window
// if it has any palindromic
// permutation
if (checkPalindrome())
{
ans++;
}
// Start and end point of window
int i = 0, j = k;
while (j < s.length)
{
// Sliding window by 1
// Decrementing count of first
// element of the window
freq[s[i++] - 97]--;
// Incrementing count of next
// element of the window
freq[s[j++] - 97]++;
// Checking current window
// character frequency count
if (checkPalindrome())
{
ans++;
}
}
// Return the final count
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given String str
String str = "abbaca";
// Window of size K
int K = 3;
// Function Call
System.out.print(countPalindromePermutation(
str.toCharArray(), K) + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # To store the frequency array freq = [0] * 26 # Function to check palindromic of # of any substring using frequency array def checkPalindrome(): # Initialise the odd count oddCnt = 0 # Traversing frequency array to # compute the count of characters # having odd frequency for x in freq: if (x % 2 == 1): oddCnt += 1 # Returns true if odd count is atmost 1 return oddCnt <= 1 # Function to count the total number # substring whose any permutations # are palindromic def countPalindromePermutation(s, k): # Computing the frequency of # first K character of the string for i in range(k): freq[ord(s[i]) - 97] += 1 # To store the count of # palindromic permutations ans = 0 # Checking for the current window # if it has any palindromic # permutation if (checkPalindrome()): ans += 1 # Start and end point of window i = 0 j = k while (j < len(s)): # Sliding window by 1 # Decrementing count of first # element of the window freq[ord(s[i]) - 97] -= 1 i += 1 # Incrementing count of next # element of the window freq[ord(s[j]) - 97] += 1 j += 1 # Checking current window # character frequency count if (checkPalindrome()): ans += 1 # Return the final count return ans # Driver Code # Given string str str = "abbaca" # Window of size K K = 3 # Function call print(countPalindromePermutation(str, K)) # This code is contributed by code_hunt
C#
// C# program for the above approach
using System;
class GFG{
// To store the frequency array
static int []freq = new int[26];
// Function to check palindromic of
// of any subString using frequency array
static bool checkPalindrome()
{
// Initialise the odd count
int oddCnt = 0;
// Traversing frequency array to
// compute the count of characters
// having odd frequency
foreach(int x in freq)
{
if (x % 2 == 1)
oddCnt++;
}
// Returns true if odd count
// is atmost 1
return oddCnt <= 1;
}
// Function to count the total number
// subString whose any permutations
// are palindromic
static int countPalindromePermutation(char []s,
int k)
{
int i = 0;
// Computing the frequency of
// first K character of the String
for(i = 0; i < k; i++)
{
freq[s[i] - 97]++;
}
// To store the count of
// palindromic permutations
int ans = 0;
// Checking for the current window
// if it has any palindromic
// permutation
if (checkPalindrome())
{
ans++;
}
// Start and end point of window
int j = k;
i = 0;
while (j < s.Length)
{
// Sliding window by 1
// Decrementing count of first
// element of the window
freq[s[i++] - 97]--;
// Incrementing count of next
// element of the window
freq[s[j++] - 97]++;
// Checking current window
// character frequency count
if (checkPalindrome())
{
ans++;
}
}
// Return the final count
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given String str
String str = "abbaca";
// Window of size K
int K = 3;
// Function Call
Console.Write(countPalindromePermutation(
str.ToCharArray(), K) + "\n");
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// To store the frequency array
var freq = Array(26).fill(0);
// Function to check palindromic of
// of any substring using frequency array
function checkPalindrome()
{
// Initialise the odd count
var oddCnt = 0;
// Traversing frequency array to
// compute the count of characters
// having odd frequency
freq.forEach(x => {
if (x % 2 == 1)
oddCnt++;
});
// Returns true if odd count is atmost 1
return oddCnt <= 1;
}
// Function to count the total number
// substring whose any permutations
// are palindromic
function countPalindromePermutation( s, k)
{
// Computing the frequency of
// first K character of the string
for (var i = 0; i < k; i++) {
freq[s[i].charCodeAt(0) - 97]++;
}
// To store the count of
// palindromic permutations
var ans = 0;
// Checking for the current window
// if it has any palindromic
// permutation
if (checkPalindrome()) {
ans++;
}
// Start and end point of window
var i = 0, j = k;
while (j < s.length) {
// Sliding window by 1
// Decrementing count of first
// element of the window
freq[s[i++].charCodeAt(0) - 97]--;
// Incrementing count of next
// element of the window
freq[s[j++].charCodeAt(0) - 97]++;
// Checking current window
// character frequency count
if (checkPalindrome()) {
ans++;
}
}
// Return the final count
return ans;
}
// Driver Code
// Given string str
var str = "abbaca";
// Window of size K
var K = 3;
// Function Call
document.write( countPalindromePermutation(str, K));
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por abhishek_padghan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA