Réorganiser la chaîne pour maximiser le nombre de sous-chaînes palindromiques en C++

Nous obtenons une chaîne "str" ​​​​de n'importe quelle longueur donnée. La tâche consiste à réorganiser les caractères de telle manière que, sans ajouter ni supprimer de caractères dans la chaîne d'entrée donnée, la plus grande sous-chaîne devienne une chaîne palindrome. Une chaîne palindrome est une chaîne de caractères disposés de telle manière qu’ils sonnent de la même manière du début à la fin.

Examinons différents scénarios d'entrée et de sortie pour cette situation -

input− string str = "itnin"

output− Réorganiser la chaîne pour maximiser le nombre de sous-chaînes palindromiques est : iinnt.

Explication- Nous obtenons une variable de type chaîne, disons str. Nous allons maintenant réorganiser les caractères de la chaîne d'entrée pour en faire une chaîne palindrome maximale et renvoyer "NON POSSIBLE" si cela n'est pas possible. Par conséquent, la sortie donnée par la chaîne d’entrée est « iinnt ».

Input− string str = "abaaaabb"

Output − Réorganiser la chaîne pour maximiser le nombre de sous-chaînes palindromiques est : aaaaabbb.

Explication - Nous donnons une variable de type chaîne, telle que str. Nous allons maintenant réorganiser les caractères de la chaîne d'entrée pour en faire une chaîne palindrome maximale et renvoyer "NON POSSIBLE" si cela n'est pas possible. Ainsi, la sortie donnée par la chaîne d'entrée est aaaaabbb'

La méthode utilisée dans le programme ci-dessous est la suivante

• Entrer une variable de chaîne Supposons que vous saisissiez str, calculiez la taille de la chaîne et la stockiez dans une variable appelée longueur.

• Passez les données à la fonction Rearr_string(str, length).

• À l'intérieur de la fonction Rearr_string(str, length)

  • déclarez un tableau de type entier de taille 26, dites arr[26] et initialisez-le avec 0.

  • Déclarez une variable temporaire "temp" de type chaîne.

  • Commencez à boucler FOR de i à 0 jusqu'à ce que i soit inférieur à la longueur. Dans la boucle, définissez arr[str[i] - 'a']++.

  • Commencez à boucler FOR de i à 0 jusqu'à ce que i soit inférieur à 26. À l'intérieur de la boucle, démarrez une autre boucle FOR de j à 0 jusqu'à ce que j soit inférieur à arr[i]. À l'intérieur de la boucle, définissez temp sur temp + (char)(97 + i).

  • Temp. de retour.

• Imprimez les résultats.

Exemple

#include <bits/stdc++.h>
using namespace std;
string Rearr_string(string str, int length){
   int arr[26] = { 0 };
   string temp = "";
   for(int i = 0; i < length; i++){
      arr[str[i] - &#39;a&#39;]++;
   }
   for(int i = 0; i < 26; i++){
      for(int j = 0; j < arr[i]; j++){
         temp = temp + (char)(97 + i);
      }
   }
   return temp;
}
int main(){
   string str = "itinn";
   int length = str.length();
   cout<<"Rearrangement of the string to maximize the number of palindromic substrings is: "<<Rearr_string(str, length);
   return 0;
}

Output

Si nous exécutons le code ci-dessus, il générera la sortie suivante

Rearrangement of the string to maximize the number of palindromic substrings is: iinnt

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!