Vérifie si tous les caractères d'une chaîne peuvent être rendus égaux en augmentant ou en diminuant

Dans ce problème, nous devons vérifier si tous les caractères de la chaîne peuvent être rendus égaux par des opérations croissantes et décroissantes. Nous pouvons obtenir le poids de chaque caractère en fonction de sa valeur ASCII et vérifier si le poids total peut être utilisé pour rendre tous les caractères égaux.

Énoncé du problème – On nous donne une chaîne str de longueur N contenant des caractères alphabétiques minuscules. Nous devons vérifier si nous pouvons rendre tous les caractères de la chaîne égaux en sélectionnant l'un des deux caractères, en augmentant un caractère, puis en décrémentant l'autre caractère de 1. Écrivez « oui » si possible, sinon écrivez « non ».

Exemple Exemple

Entrée– str = 'aedb

sortie-str = 'aedb

Explication - « a » peut augmenter de 2 et « e » peut diminuer de 2. En même temps, « b » peut être incrémenté de 1 et « d » peut être incrémenté de 1. Par conséquent, la chaîne résultante peut être « cccc ».

Entrée– str = 'abd'

Sortie-"Non"

Explication – Nous ne pouvons pas rendre tous les caractères d'une chaîne égaux en augmentant et en diminuant

Entrez -'g'

Sortie - 'Oui'

Explication – Une chaîne ne contient qu'un seul caractère, donc tous les caractères de la chaîne sont déjà égaux

Méthode 1

Dans cette méthode, nous calculerons le poids total des caractères de la chaîne. Les poids des caractères sont définis comme « a » = 1, « b » = 2, « c » = 3,…, « z » = 26. Ainsi, si nous divisons le poids total par la longueur de la chaîne, nous pouvons dire qu’en augmentant un caractère et en diminuant un autre, nous rendons tous les caractères de la chaîne égaux.

Algorithme

• Définissez la variable "len" et utilisez la méthode size() pour stocker la taille de la chaîne.

• Définissez la variable "totalWeight" pour stocker le poids total de tous les caractères d'une chaîne donnée

• Obtenez le poids d'un caractère spécifique en utilisant le code ASCII de chaque caractère et ajoutez-le à la variable "totalWeight".

• Renvoie vrai si la valeur de "totalWeight" est divisible par "len". Sinon, renvoie faux.

Exemple

#include <iostream>
using namespace std;

// function to check if all characters of a string can be made equal by incrementing or decrementing by 1
bool canMakeEqual(string str){
   int len = str.size();
   // store sum of ASCII values of characters
   int totalWeight = 0;
   // Iterate over the string
   for (int i = 0; i < len; i++){
      // get the ASCII value of each character
      totalWeight += str[i] - 'a' + 1;
   }
   return (totalWeight % len == 0);
}
int main(){
   string str = "aedb";
   if (canMakeEqual(str))
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

Sortie

Yes

Complexité temporelle - O(N) puisque nous parcourons la chaîne.

Complexité spatiale - O(1) car nous utilisons un espace constant.

Conclusion

Nous avons appris à vérifier si tous les caractères d'une chaîne peuvent être égaux en augmentant et en diminuant la valeur ASCII du caractère. Nous résolvons ce problème en termes de « poids total ». L'utilisateur peut également essayer de trouver la chaîne résultante. Pour trouver la chaîne résultante, recherchez la valeur ASCII correspondant à (totalWeight/len) et ajoutez les caractères "len" à la chaîne donnée.

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!