Dada una string s y un entero X , nuestra tarea es encontrar el número de strings palindrómicas distintas de longitud X de la string dada.
Ejemplos:
Entrada: s = “aaa”, X = 2
Salida: 1
Explicación:
Aquí todos los caracteres de la string son iguales, por lo que solo podemos hacer una string diferente {aa} de longitud 2.Entrada: s = “aabaabbc”, X = 3
Salida: 6
Explicación:
Para hacer una string palindrómica de longitud 3 tenemos 6 strings posibles aaa, aba, aca, bab, bcb, bbb.
Enfoque ingenuo: el método ingenuo es generar todas las subsecuencias posibles de longitud X, luego verificar si esa subsecuencia forma un palíndromo o no.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(X)
Enfoque eficiente: la idea es encontrar la frecuencia de todos los caracteres de la string. Cuente los diferentes números de los caracteres que podemos poner en la posición particular y disminuya el número de conteo en 2 porque para la string palindrómica, la posición (i) y (X – i) serán las mismas. Si la longitud de X es impar, entonces tenemos que poner el único carácter único en esa posición X/2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count different
// palindromic string of length X
// from the given string S
#include <bits/stdc++.h>
using namespace std;
// Function to count different
// palindromic string of length X
// from the given string S
long long findways(string s, int x)
{
// Base case
if (x > (int)s.length())
return 0;
long long int n = (int)s.length();
// Create the frequency array
int freq[26];
// initialize frequency array with 0
memset(freq, 0, sizeof freq);
// Count the frequency in the string
for (int i = 0; i < n; ++i)
freq[s[i] - 'a']++;
multiset<int> se;
for (int i = 0; i < 26; ++i)
if (freq[i] > 0)
// Store frequency of the char
se.insert(freq[i]);
long long ans = 1;
for (int i = 0; i < x / 2; ++i) {
long long int count = 0;
for (auto u : se) {
// check the frequency which
// is greater than zero
if (u >= 2)
// No. of different char we can
// put at the position of
// the i and x - i
count++;
}
if (count == 0)
return 0;
else
ans = ans * count;
// Iterator pointing to the
// last element of the set
auto p = se.end();
p--;
int val = *p;
se.erase(p);
if (val > 2)
// decrease the value of the char
// we put on the position i and n - i
se.insert(val - 2);
}
if (x % 2 != 0) {
long long int count = 0;
for (auto u : se)
// different no of char we can
// put at the position x/2
if (u > 0)
count++;
ans = ans * count;
}
// Return total no of
// different string
return ans;
}
// Driver code
int main()
{
string s = "aaa";
int x = 2;
cout << findways(s, x);
return 0;
}
Java
// Java implementation to count different
// palindromic string of length X from the
// given string S
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
class GFG{
// Function to count different
// palindromic string of length X
// from the given string S
static int findways(String s, int x)
{
// Base case
if (x > s.length())
return 0;
int n = s.length();
// Create the frequency array
int[] freq = new int[26];
// initialize frequency array with 0
Arrays.fill(freq, 0);
// Count the frequency in the string
for(int i = 0; i < n; ++i)
freq[s.charAt(i) - 'a']++;
// multiset<int> se;
Set<Integer> se = new HashSet<>();
for(int i = 0; i < 26; ++i)
if (freq[i] > 0)
// Store frequency of the char
se.add(freq[i]);
int ans = 1;
for(int i = 0; i < x / 2; ++i)
{
int count = 0;
for(int u : se)
{
// Check the frequency which
// is greater than zero
if (u >= 2)
// No. of different char we can
// put at the position of
// the i and x - i
count++;
}
if (count == 0)
return 0;
else
ans = ans * count;
// Iterator pointing to the
// last element of the set
int p = (int)se.toArray()[se.size() - 1];
int val = p;
se.remove(p);
if (val > 2)
// Decrease the value of the char
// we put on the position i and n - i
se.add(val - 2);
}
if (x % 2 != 0)
{
int count = 0;
for(int u : se)
// Different no of char we can
// put at the position x/2
if (u > 0)
count++;
ans = ans * count;
}
// Return total no of
// different string
return ans;
}
// Driver code
public static void main(String[] args)
{
String s = "aaa";
int x = 2;
System.out.println(findways(s, x));
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 implementation to count
# different palindromic string of
# length X from the given string S
# Function to count different
# palindromic string of length X
# from the given string S
def findways(s, x):
# Base case
if(x > len(s)):
return 0
n = len(s)
# Create the frequency array
# initialize frequency array with 0
freq = [0] * 26
# Count the frequency in the string
for i in range(n):
freq[ord(s[i]) - ord('a')] += 1
se = set()
for i in range(26):
if(freq[i] > 0):
# Store frequency of the char
se.add(freq[i])
ans = 1
for i in range(x // 2):
count = 0
for u in se:
# Check the frequency which
# is greater than zero
if(u >= 2):
# No. of different char we can
# put at the position of
# the i and x - i
count += 1
if(count == 0):
return 0
else:
ans *= count
# Iterator pointing to the
# last element of the set
p = list(se)
val = p[-1]
p.pop(-1)
se = set(p)
if(val > 2):
# Decrease the value of the char
# we put on the position i and n - i
se.add(val - 2)
if(x % 2 != 0):
count = 0
for u in se:
# Different no of char we can
# put at the position x/2
if(u > 0):
count += 1
ans = ans * count
# Return total no of
# different string
return ans
# Driver code
if __name__ == '__main__':
s = "aaa"
x = 2
print(findways(s, x))
# This code is contributed by Shivam Singh
C#
// C# implementation to count different
// palindromic string of length X from the
// given string S
using System;
using System.Collections.Generic;
class GFG {
// Function to count different
// palindromic string of length X
// from the given string S
static int findways(string s, int x)
{
// Base case
if (x > s.Length)
return 0;
int n = s.Length;
// Create the frequency array
int[] freq = new int[26];
// Count the frequency in the string
for (int i = 0; i < n; ++i)
freq[s[i] - 'a']++;
// multiset<int> se;
HashSet<int> se = new HashSet<int>();
for (int i = 0; i < 26; ++i)
if (freq[i] > 0)
// Store frequency of the char
se.Add(freq[i]);
int ans = 1;
for (int i = 0; i < x / 2; ++i)
{
int count = 0;
foreach(int u in se)
{
// Check the frequency which
// is greater than zero
if (u >= 2)
// No. of different char we can
// put at the position of
// the i and x - i
count++;
}
if (count == 0)
return 0;
else
ans = ans * count;
// Iterator pointing to the
// last element of the set
int[] arr = new int[se.Count];
se.CopyTo(arr);
int p = arr[se.Count - 1];
int val = p;
se.Remove(p);
if (val > 2)
// Decrease the value of the char
// we put on the position i and n - i
se.Add(val - 2);
}
if (x % 2 != 0)
{
int count = 0;
foreach(int u in se)
// Different no of char we can
// put at the position x/2
if (u > 0) count++;
ans = ans * count;
}
// Return total no of
// different string
return ans;
}
// Driver code
static public void Main()
{
string s = "aaa";
int x = 2;
Console.WriteLine(findways(s, x));
}
}
// This code is contributed by dharanendralv23
Javascript
<script>
// Javascript implementation to count different
// palindromic string of length X
// from the given string S
// Function to count different
// palindromic string of length X
// from the given string S
function findways(s, x)
{
// Base case
if (x > s.length)
return 0;
var n = s.length;
// Create the frequency array
var freq = Array(26).fill(0);
// Count the frequency in the string
for (var i = 0; i < n; ++i)
freq[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
var se = [];
for (var i = 0; i < 26; ++i)
if (freq[i] > 0)
// Store frequency of the char
se.push(freq[i]);
var ans = 1;
for (var i = 0; i < x / 2; ++i) {
var count = 0;
se.forEach(u => {
// check the frequency which
// is greater than zero
if (u >= 2)
// No. of different char we can
// put at the position of
// the i and x - i
count++;
});
if (count == 0)
return 0;
else
ans = ans * count;
se.sort((a,b)=>a-b)
var val = se[se.length-1]
// Iterator pointing to the
// last element of the set
se.pop();
if (val > 2)
// decrease the value of the char
// we put on the position i and n - i
se.push(val - 2);
}
if (x % 2 != 0) {
var count = 0;
se.forEach(u => {
// different no of char we can
// put at the position x/2
if (u > 0)
count++;
});
ans = ans * count;
}
// Return total no of
// different string
return ans;
}
// Driver code
var s = "aaa";
var x = 2;
document.write( findways(s, x));
// This code is contributed by noob2000.
</script>
Producción:
1
Complejidad temporal: O(N + 26 * X)