En utilisant les caractères donnés, comptez le nombre de chaînes de longueur 3 contenant au moins 2 caractères différents

Donnez-nous trois entiers "a", "b" et "c", représentant la fréquence d'apparition de trois caractères différents "A", "B" et "C". Nous devons trouver le nombre de chaînes différentes qui peuvent être formées à l'aide de ces caractères, et au moins deux caractères différents doivent être présents dans la chaîne formée. Nous verrons deux façons de résoudre ce problème, l’une est naïve et l’autre mathématique.

Exemple

Input 1: a = 3, b = 2, c = 4 

Output:  3 

Instructions

Nous pouvons créer trois chaînes "ABC", "ABC" et "ACC". Nous utilisons « A » 3 fois, « B » 2 fois et « C » 4 fois dans ces chaînes, ce qui est la même fréquence ou moins que celle qui leur est donnée, et toutes les chaînes contiennent au moins 2 caractères différents. p>

Input 2: a = 1, b = 3, c = 10

Output: 4

Instructions

Nous pouvons créer les chaînes "ACC", "BCC", "BCC" et "BCC". Nous avons utilisé tous les caractères donnés à l'exception des deux "C", car il n'y a pas d'autres caractères avec lesquels créer une nouvelle chaîne. Si nous avions essayé d’autres combinaisons, le nombre final de cordes aurait été moindre.

Méthode naïve

Le moyen le plus simple est de trouver toutes les combinaisons possibles d'une fréquence donnée, mais le problème est que cela prend beaucoup de temps et est extrêmement inefficace.

Nous devons générer toutes les sous-chaînes possibles, et si nos nombres sont grands, cela prendra beaucoup de temps et d'espace qu'un ordinateur ne peut pas gérer.

Méthodes mathématiques

Idées

L'idée derrière cette approche est que nous avons besoin d'au moins deux caractères distincts dans la chaîne, nous essaierons donc toujours de nous concentrer sur le caractère le moins fréquent.

Le nombre maximum de chaînes que nous pouvons créer est de (a+b+c)/3, et le nombre possible ne dépend que de la fréquence d'apparition d'au moins deux.

Supposons que si au moins deux fréquences sont x et y, alors leur somme est supérieure ou égale à (a+b+c)/3 alors nous pouvons imprimer cette valeur comme réponse, sinon la somme de x et y est la réponse.

Mise en œuvre

Nous avons vu des exemples et des idées pour trouver des solutions, commençons maintenant à implémenter le code -

• Tout d'abord, nous allons créer une fonction qui accepte trois entiers et renvoie un entier.

• Dans la fonction, nous stockons d'abord tous les entiers dans un vecteur, puis trions le vecteur pour obtenir l'entier de fréquence minimale.

• Nous obtiendrons la somme de tous les éléments donnés puis diviserons par 3 pour obtenir le nombre maximum de chaînes que nous pouvons créer.

• Plus tard, nous comparerons la valeur de la plus grande chaîne avec la valeur de la plus petite somme de deux fréquences. Si la somme est plus petite, nous mettons à jour la chaîne maximale pour qu'elle soit la somme d'au moins deux éléments de fréquence.

• Enfin, nous renverrons la valeur de la plus grande chaîne possible et l'imprimerons dans la fonction principale.

Exemple

#include <bits/stdc++.h>
using namespace std;
int count(int a, int b, int c){
   // storing the values in the vector 
   vector<int>temp(3);
   temp[0] = a;
   temp[1] = b;
   temp[2] = c; 
   
   // sorting the vector to get the minimum two elements 
   sort(temp.begin(), temp.end());
   
   // counting the sum of all the elements 
   int maxStrings = (a+b+c)/3;    
   if(temp[0] + temp[1] < maxStrings){
      maxStrings = temp[0] + temp[1];
   }    
   return maxStrings; // returning the final answer
}
int main(){

   // given numbers 
   int a = 3;
   int b = 2;
   int c = 4;
   cout<<"The count of 3 length strings using given characters containing at least 2 different characters is "<<count(a,b,c)<<endl;   
   return 0;
}

Sortie

The count of 3 length strings using given characters containing at least 2 different characters is 3

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(1) ou constante car nous n'utilisons aucune boucle ou appel récursif pour obtenir le résultat.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons pas d'espace supplémentaire ici.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme pour trouver 3 chaînes de longueur avec un nombre de 3 en utilisant un caractère donné contenant au moins 2 caractères différents. Nous avons discuté de méthodes simples et mis en œuvre des méthodes mathématiques avec une complexité temporelle et spatiale constante, c'est-à-dire O (1).

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!