Étant donné un tableau, trouvez la somme maximale des longueurs de deux chaînes qui n'ont pas les mêmes caractères.

Le but de cet article est d'implémenter un programme pour maximiser la somme des longueurs d'une paire de chaînes qui n'ont pas de caractères communs dans un tableau donné. Par définition, une chaîne est une collection de caractères.

Énoncé du problème

Implémentez un programme pour maximiser la somme des longueurs d'une paire de chaînes sans caractères communs dans un tableau donné.

Exemple 1

Let us consider the Input array: 
a[] = [“efgh”, “hat”, “fto”, “car”, “wxyz”, “fan”]

Output obtained: 8

Instructions

Il n'y a pas de caractères communs dans les chaînes "abcd" et "wxyz". En conséquence, la longueur combinée des deux chaînes est de 4 + 4, ce qui est égal à 8, la longueur la plus longue parmi toutes les paires possibles.

Exemple 2

Let us consider the Input array: 
a[] = [“abc”, “cat”, “bat”, “hij”, “abcd”, “an”, "can"]

Output obtained: 7

Instructions

Il n'y a pas de caractères communs dans les chaînes "abcd" et "hij". En conséquence, la longueur combinée des deux chaînes est de 4 + 3, ce qui équivaut à 8, la longueur la plus longue parmi toutes les paires possibles.

Exemple 3

Let us consider the Input array: 
a[] = [“xyz”, “zip”, “lmno”, “lot”, “abcdx”, “yo”]

Output obtained: 9

Instructions

Il n'y a pas de caractères communs dans les chaînes "abcdx" et "lmno". En conséquence, la longueur combinée des deux chaînes est de 5 + 4, ce qui équivaut à 9 et constitue la longueur la plus longue parmi toutes les paires possibles.

Exemple 4

Let us consider the Input array: 
a[] = [“abc”, “coat”, “bat”, “hij”, “abcd”, “an”]

Output obtained: 7

Instructions

Il n'y a pas de caractères communs dans les chaînes "coat" et "hij". En conséquence, la longueur combinée des deux chaînes est de 4 + 3, ce qui équivaut à 8, la longueur la plus longue parmi toutes les paires possibles.

Solution

Pour maximiser la somme des longueurs d'une paire de chaînes sans caractères communs dans un tableau donné, nous utilisons l'approche suivante.

Un moyen de résoudre ce problème ou de trouver un moyen de maximiser la somme des longueurs d'une paire de chaînes sans caractères communs dans le tableau donné est la suivante. Cela dit, le moyen le plus simple de résoudre le problème ci-dessus consiste à créer chaque paire potentielle de tableaux de chaînes, puis à afficher la somme maximale des longueurs de chaîne de toutes les paires possibles sans caractères en commun. < /p>

En utilisant le concept d'opérations sur bits, la stratégie ci-dessus peut également être améliorée. Le but ici est de convertir chaque chaîne en son entier équivalent masqué par bits avant d'identifier des paires de chaînes qui ne partagent aucun caractère commun et qui ont la somme de longueurs la plus longue possible.

BitMasking est notre thème actuel. Qu'est-ce qu'un petit masque exactement ?

Nous devons d’abord nous rappeler ce qu’est un nombre entier. Les entiers ne sont que des collections de bits enchaînés. Le concept de masquage de bits consiste à représenter graphiquement les nombres sous forme binaire.

En termes simples, un « masque de bits » est un nombre binaire qui peut spécifier n'importe quoi.

Algorithme

Vous trouverez ci-dessous l'algorithme permettant d'implémenter un programme permettant de maximiser la somme des longueurs d'une paire de chaînes qui n'ont aucun caractère en commun dans un tableau donné.

• Étape 1 - Commencer

• Étape 2 - Créez une fonction memset() pour initialiser le tableau de masques de bits avec des zéros. Un masque de bits de taille initiale L utilisé pour enregistrer le OU au niveau du bit des chaînes dans le tableau arr[] de chaînes.

• Étape 3 - Pour stocker la réponse, définissez la valeur de la variable maxLength sur 0.

• Étape 4 - Effectuez ce qui suit en itérant sur la plage [0, L] en utilisant la variable i -

• Étape 5 - Définissez la valeur de bitmask[i] comme mask[i]|1(arr[i][j] - 'a') et parcourez la plage [0, S], où S est un taille de la chaîne.

• Étape 6 - Utilisez la variable entière j pour parcourir la plage [0, i] et définissez la valeur de maxLength sur la valeur maximale de arr[i].length() + if bitmask[i] et bitmask[ j] sont au niveau du bit Et le résultat n'est pas 0, alors arr[j].length().

• Étape 7 - Imprimez enfin les résultats obtenus.

• Étape 8 - Arrêtez

Exemple : programme C

Il s'agit d'une implémentation de programme C de l'algorithme écrit ci-dessus pour maximiser la somme des longueurs d'une paire de chaînes sans caractères en commun dans un tableau donné

Il s'agit d'une implémentation de programme C de l'algorithme écrit ci-dessus pour maximiser la somme des longueurs d'une paire de chaînes sans caractères en commun dans un tableau donné

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 26
// Defining a function maxSumLength used to determine the longest combinedlength of two strings with no shared characters
int maxSumLength(char* arr[], int n){

   // Stores the bitmask of each string
   int bitmask[n];
   
   // Initialize the bitmask of each string to 0
   memset(bitmask, 0, sizeof(bitmask));
   
   // set the res to number 0
   int res = 0;
   
   // Now iterating this
   for (int i = 0; i < n; ++i) {
   
      // For every given elements 
      for (int j = 0; j < strlen(arr[i]); ++j) {
      
         // If the ith value of bitmask |= 1 then left shift that particular character - a
         bitmask[i] |= 1 << (arr[i][j] - 'a');
      }
      
      // Check for all the ith element, whether the ith and jth values of the
      // mask are not equal, if so add and also maximize those
      for (int j = 0; j < i; ++j) {
         if (!(bitmask[i] & bitmask[j])) {
            res = (res > strlen(arr[i]) + strlen(arr[j])) ? res : strlen(arr[i]) + strlen(arr[j]);
         }
      }
   }
   
   // the obtained maximum sum of the lengths of the strings obtained is returned
   return res;
}

int main(){
   char* arr[] = { "abcd", "def", "xyz" };
   int n = sizeof(arr) / sizeof(arr[0]);
   printf("%d", maxSumLength(arr, n));
   return 0;
}

Sortie

7

Conclusion

De même, nous pouvons maximiser la somme des longueurs d'une paire de chaînes qui n'ont pas de caractères communs dans le tableau donné.

Cet article aborde le défi consistant à obtenir un programme permettant de maximiser la somme des longueurs d'une paire de chaînes qui n'ont aucun caractère en commun dans un tableau donné.

Le code de programmation C est fourni ici avec un algorithme pour maximiser la somme des longueurs d'une paire de chaînes qui n'ont pas de caractères communs dans un tableau donné.

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!