Dada una string S que consta de alfabetos en minúsculas, la tarea es verificar si la string dada se puede reorganizar de modo que la string se pueda dividir en substrings palindrómicas que no se superpongan de al menos 2 de longitud . Si se encuentra que es cierto , escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S = “aaaabbcdd”
Salida: Sí
Explicación: Reorganice la string dada S a “acaaabbdd”, que se puede dividir en substrings palindrómicas no superpuestas “aca”, “aa”, “bb”, “dd”.Entrada: S = “ccddgggggefs”
Salida: No
Enfoque: el problema dado se puede resolver reorganizando los caracteres de la string en substrings de longitud 2 , que consisten en un solo carácter distinto. Si existe algún carácter con frecuencia impar, entonces lo coloca en medio de las substrings palindrómicas de longitud 2 .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar , por ejemplo, frecuencia[] de tamaño 26 , para almacenar la frecuencia de cada carácter presente en la string S.
- Atraviese la string S dada y actualice la frecuencia de cada carácter en la array frecuencia[] .
- Inicialice dos variables, digamos impar y par como 0 , para almacenar la frecuencia de los elementos impares y el número de substrings palindrómicas de longitud 2 formadas.
- Atraviese la array frecuencia[] y si el valor de frecuencia[i] es mayor que 0 , agregue el valor (frecuencia[i] y 1) y (frecuencia[i]/2) a la variable par e impar respectivamente.
- Después de completar los pasos anteriores, si el valor de impar es par como máximo , 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 <bits/stdc++.h>
using namespace std;
// Function to check if a string can be
// modified such that it can be split into
// palindromic substrings of length >= 2
void canSplit(string& S)
{
// Stores frequencies of characters
vector<int> frequency(26, 0);
int cnt_singles = 0;
int k = 0;
// Traverse the string
for (int i = 0; i < S.length(); i++)
// Update frequency
// of each character
frequency[S[i] - 'a']++;
int odd = 0, eve = 0;
// Traverse the frequency array
for (int i = 0; i < 26; i++) {
// Update values of odd and eve
if (frequency[i]) {
odd += (frequency[i] & 1);
eve += frequency[i] / 2;
}
}
// Print the result
if (eve >= odd)
cout << "Yes";
else
cout << "No";
}
// Driver Code
int main()
{
string S = "aaabbbccc";
canSplit(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
// modified such that it can be split into
// palindromic substrings of length >= 2
static void canSplit(String S)
{
// Stores frequencies of characters
int frequency[] = new int[26];
int cnt_singles = 0;
int k = 0;
// Traverse the string
for (int i = 0; i < S.length(); i++)
// Update frequency
// of each character
frequency[S.charAt(i) - 'a']++;
int odd = 0, eve = 0;
// Traverse the frequency array
for (int i = 0; i < 26; i++) {
// Update values of odd and eve
if (frequency[i] != 0) {
odd += (frequency[i] & 1);
eve += frequency[i] / 2;
}
}
// Print the result
if (eve >= odd)
System.out.println("Yes");
else
System.out.println("No");
}
// Driver Code
public static void main(String[] args)
{
String S = "aaabbbccc";
canSplit(S);
}
}
Python3
# Python3 program for the above approach
# Function to check if a string can be
# modified such that it can be split into
# palindromic substrings of length >= 2
def canSplit(S):
# Stores frequencies of characters
frequency = [0] * 26
cnt_singles = 0
k = 0
# Traverse the string
for i in range(len(S)):
# Update frequency
# of each character
frequency[ord(S[i]) - ord('a')] += 1
odd = 0
eve = 0
# Traverse the frequency array
for i in range(26):
# Update values of odd and eve
if (frequency[i]):
odd += (frequency[i] & 1)
eve += frequency[i] // 2
# Print the result
if (eve >= odd):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == "__main__" :
S = "aaabbbccc"
canSplit(S)
# This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to check if a string can be
// modified such that it can be split into
// palindromic substrings of length >= 2
static void canSplit(string S)
{
// Stores frequencies of characters
int []frequency = new int[26];
int cnt_singles = 0;
int k = 0;
// Traverse the string
for (int i = 0; i < S.Length; i++)
// Update frequency
// of each character
frequency[S[i] - 'a']++;
int odd = 0, eve = 0;
// Traverse the frequency array
for (int i = 0; i < 26; i++)
{
// Update values of odd and eve
if (frequency[i] != 0)
{
odd += (frequency[i] & 1);
eve += frequency[i] / 2;
}
}
// Print the result
if (eve >= odd)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
// Driver Code
public static void Main(string[] args)
{
string S = "aaabbbccc";
canSplit(S);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Function to check if a string can be
// modified such that it can be split into
// palindromic substrings of length >= 2
function canSplit(S){
// Stores frequencies of characters
let frequency = new Array(26).fill(0)
let cnt_singles = 0
let k = 0
// Traverse the string
for(let i = 0; i < S.length; i++){
// Update frequency
// of each character
frequency[S.charCodeAt(i) - 'a'.charCodeAt(0)] += 1
}
let odd = 0
let eve = 0
// Traverse the frequency array
for(let i = 0; i < 26; i++){
// Update values of odd and eve
if (frequency[i]){
odd += (frequency[i] & 1)
eve += frequency[i] // 2
}
}
// document.write the result
if (eve >= odd){
document.write("Yes")
}
else{
document.write("No")
}
}
// Driver Code
let S = "aaabbbccc"
canSplit(S)
// This code is contributed by gfgking
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA