Dada una string S que consta de N alfabetos en minúsculas, la tarea es verificar si todas las strings de al menos una longitud de 2 formadas al seleccionar cada carácter de la string S solo una vez son palindrómicas o no . Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S = “abbbaddzcz”
Salida: Sí
Explicación: Las strings palindrómicas de longitud superior a 1 son { “aa”, “bbb”, “dd”, “zcz”} y todos los caracteres de la string dada se usan solo una vez . Por lo tanto, imprima «Sí».Entrada: S = “abcd”
Salida: No
Enfoque: la idea es dividir la string en strings palindrómicas de longitud uniforme, y si existe un carácter que tenga una frecuencia 1 , entonces emparejarlo con una string palindrómica de longitud uniforme. Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos freq[] , de tamaño 26 , para almacenar la frecuencia de cada carácter presente en la string .
- Itere sobre los caracteres de la string S dada y actualice la frecuencia de cada carácter en la array freq[] .
- Inicialice dos variables, digamos O y E , para almacenar el recuento de caracteres únicos y caracteres que tienen frecuencias pares, respectivamente.
- Recorra la array freq[] y si freq[i] es igual a 1 , entonces incremente O en 1 . De lo contrario, incremente E en 1 .
- Compruebe si E ≥ O , luego escriba “Sí” . De lo contrario, realice los siguientes pasos:
- Actualice O a O – E , para almacenar los caracteres únicos restantes después del emparejamiento.
- Atraviese la array freq[] y si el valor de O es como máximo 0 , salga del bucle . De lo contrario, actualice O a O – (freq[i]/2) y luego incremente O en 1 .
- Después de completar los pasos anteriores, si el valor de O ≤ 0 , imprima «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to check if a string can be
// split into palindromic strings of at
// least length 2 by including every
// character exactly once
void checkPalindrome(string& s)
{
// Stores the frequency
// of each character
int a[26] = { 0 };
// Store the frequency of
// characters with frequencies
// 1 and even respectively
int o = 0, e = 0;
// Traverse the string s
for (int i = 0; s[i] != '\0'; i++)
a[(int)s[i] - 97]++;
// Iterate over all the characters
for (int i = 0; i < 26; i++) {
// If the frequency is 1
if (a[i] == 1)
o++;
// If frequency is even
else if (a[i] % 2 == 0
and a[i] != 0)
e += (a[i] / 2);
}
// Print the result
if (e >= o)
cout << "Yes";
else {
// Stores the number of characters
// with frequency equal to 1 that
// are not part of a palindromic string
o = o - e;
// Iterate over all the characters
for (int i = 0; i < 26; i++) {
// If o becomes less than 0,
// then break out of the loop
if (o <= 0)
break;
// If frequency of the current
// character is > 2 and is odd
if (o > 0
and a[i] % 2 == 1
and a[i] > 2) {
int k = o;
// Update the value of o
o = o - a[i] / 2;
// If a single character
// is still remaining
if (o > 0 or 2 * k + 1 == a[i]) {
// Increment o by 1
o++;
// Set a[i] to 1
a[i] = 1;
}
}
}
// Print the result
if (o <= 0)
cout << "Yes";
else
cout << "No";
}
}
// Driver Code
int main()
{
string S = "abbbaddzcz";
checkPalindrome(S);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if a string can be
// split into palindromic strings of at
// least length 2 by including every
// character exactly once
static void checkPalindrome(String s)
{
// Stores the frequency
// of each character
int a[] = new int[26];
// Store the frequency of
// characters with frequencies
// 1 and even respectively
int o = 0, e = 0;
// Traverse the string s
for(int i = 0; i < s.length(); i++)
a[s.charAt(i) - 'a']++;
// Iterate over all the characters
for(int i = 0; i < 26; i++)
{
// If the frequency is 1
if (a[i] == 1)
o++;
// If frequency is even
else if (a[i] % 2 == 0 && a[i] != 0)
e += (a[i] / 2);
}
// Print the result
if (e >= o)
System.out.println("Yes");
else
{
// Stores the number of characters
// with frequency equal to 1 that
// are not part of a palindromic string
o = o - e;
// Iterate over all the characters
for(int i = 0; i < 26; i++)
{
// If o becomes less than 0,
// then break out of the loop
if (o <= 0)
break;
// If frequency of the current
// character is > 2 and is odd
if (o > 0 && a[i] % 2 == 1 && a[i] > 2)
{
int k = o;
// Update the value of o
o = o - a[i] / 2;
// If a single character
// is still remaining
if (o > 0 || 2 * k + 1 == a[i])
{
// Increment o by 1
o++;
// Set a[i] to 1
a[i] = 1;
}
}
}
// Print the result
if (o <= 0)
System.out.println("Yes");
else
System.out.println("No");
}
}
// Driver Code
public static void main(String[] args)
{
String S = "abbbaddzcz";
checkPalindrome(S);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to check if a string can be
# split into palindromic strings of at
# least length 2 by including every
# character exactly once
def checkPalindrome(s):
# Stores the frequency
# of each character
a = [0] * 26
# Store the frequency of
# characters with frequencies
# 1 and even respectively
o, e = 0, 0
# Traverse the string s
for i in s:
a[ord(i) - 97] += 1
# Iterate over all the characters
for i in range(26):
# If the frequency is 1
if (a[i] == 1):
o += 1
# If frequency is even
elif (a[i] % 2 == 0 and a[i] != 0):
e += (a[i] // 2)
# Print the result
if (e >= o):
print("Yes")
else:
# Stores the number of characters
# with frequency equal to 1 that
# are not part of a palindromic string
o = o - e
# Iterate over all the characters
for i in range(26):
# If o becomes less than 0,
# then break out of the loop
if (o <= 0):
break
# If frequency of the current
# character is > 2 and is odd
if (o > 0 and a[i] % 2 == 1 and a[i] > 2):
k = o
# Update the value of o
o = o - a[i] // 2
# If a single character
# is still remaining
if (o > 0 or 2 * k + 1 == a[i]):
# Increment o by 1
o += 1
# Set a[i] to 1
a[i] = 1
# Print the result
if (o <= 0):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == '__main__':
S = "abbbaddzcz"
checkPalindrome(S)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if a string can be
// split into palindromic strings of at
// least length 2 by including every
// character exactly once
static void checkPalindrome(string s)
{
// Stores the frequency
// of each character
int[] a = new int[26];
// Store the frequency of
// characters with frequencies
// 1 and even respectively
int o = 0, e = 0;
// Traverse the string s
for(int i = 0; i < s.Length; i++)
a[s[i] - 'a']++;
// Iterate over all the characters
for(int i = 0; i < 26; i++)
{
// If the frequency is 1
if (a[i] == 1)
o++;
// If frequency is even
else if (a[i] % 2 == 0 && a[i] != 0)
e += (a[i] / 2);
}
// Print the result
if (e >= o)
Console.WriteLine("Yes");
else
{
// Stores the number of characters
// with frequency equal to 1 that
// are not part of a palindromic string
o = o - e;
// Iterate over all the characters
for(int i = 0; i < 26; i++)
{
// If o becomes less than 0,
// then break out of the loop
if (o <= 0)
break;
// If frequency of the current
// character is > 2 and is odd
if (o > 0 && a[i] % 2 == 1 && a[i] > 2)
{
int k = o;
// Update the value of o
o = o - a[i] / 2;
// If a single character
// is still remaining
if (o > 0 || 2 * k + 1 == a[i])
{
// Increment o by 1
o++;
// Set a[i] to 1
a[i] = 1;
}
}
}
// Print the result
if (o <= 0)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// Driver code
static void Main()
{
string S = "abbbaddzcz";
checkPalindrome(S);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to check if a string can be
// split into palindromic strings of at
// least length 2 by including every
// character exactly once
function checkPalindrome( s )
{
// Stores the frequency
// of each character
let a = [0]
// Store the frequency of
// characters with frequencies
// 1 and even respectively
let o = 0, e = 0;
// Traverse the string s
for (let i = 0; i<s.length; i++)
a[s.charCodeAt(i) - 97]++;
// Iterate over all the characters
for (let i = 0; i < 26; i++) {
// If the frequency is 1
if (a[i] == 1)
o++;
// If frequency is even
else if (a[i] % 2 == 0 && a[i] != 0)
e += (a[i] / 2);
}
// Print the result
if (e >= o)
document.write("Yes")
else {
// Stores the number of characters
// with frequency equal to 1 that
// are not part of a palindromic string
o = o - e;
// Iterate over all the characters
for (let i = 0; i < 26; i++)
{
// If o becomes less than 0,
// then break out of the loop
if (o <= 0)
break;
// If frequency of the current
// character is > 2 and is odd
if (o > 0 && a[i] % 2 == 1 && a[i] > 2)
{
let k = o;
// Update the value of o
o = o - a[i] / 2;
// If a single character
// is still remaining
if (o > 0 || 2 * k + 1 == a[i])
{
// Increment o by 1
o++;
// Set a[i] to 1
a[i] = 1;
}
}
}
// Print the result
if (o <= 0)
document.write("Yes")
else
document.write("No")
}
}
// Driver Code
let S = "abbbaddzcz";
checkPalindrome(S);
// This code is contributed by Hritik
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)