Given an array, find the maximum sum of the lengths of two strings that do not have the same characters.

The purpose of this article is to implement a program to maximize the sum of the lengths of a pair of strings with no common characters in a given array. By definition, a string is a collection of characters.

Problem Statement

Implement a program to maximize the sum of the lengths of a pair of strings with no common characters in a given array.

Example 1

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

Output obtained: 8

illustrate

There are no common characters in the strings "abcd" and "wxyz". As a result, the combined length of the two strings is 4 4, which is equal to 8 and is the longest length among all feasible pairs.

Example 2

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

Output obtained: 7

illustrate

There are no common characters in the strings "abcd" and "hij". As a result, the combined length of the two strings is 4 3, which is equal to 8 and is the longest length among all feasible pairs.

Example 3

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

Output obtained: 9

illustrate

There are no common characters in the strings "abcdx" and "lmno". As a result, the combined length of the two strings is 5 4, which is equal to 9 and is the longest length among all feasible pairs.

Example 4

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

Output obtained: 7

illustrate

There are no common characters in the strings "coat" and "hij". As a result, the combined length of the two strings is 4 3, which is equal to 8 and is the longest length among all feasible pairs.

solution

To maximize the sum of the lengths of a pair of strings that have no common characters in a given array, we use the following approach.

Solve this problem or find a way to maximize the sum of the lengths of a pair of strings with no common characters in the given array as follows. That said, the most straightforward way to deal with the above problem is to create each potential pair of string arrays and then display the maximum sum of the string lengths of all possible pairs with no characters in common. < /p>

Using the concept of bit operations, the above strategy can also be improved. The goal here is to convert each string into its equivalent bit-masked integer before identifying pairs of strings that share no common characters and have the longest possible sum of lengths.

BitMasking is our current topic. What exactly is a bit mask?

We must first remember what an integer is. Integers are just collections of bits strung together. The concept of bit masking is to represent numbers graphically using binary form.

Simply put, a "bitmask" is a binary number that can specify anything.

algorithm

Given below is the algorithm for implementing a program to maximize the sum of lengths of a pair of strings that have no characters in common in a given array.

• Step 1 - Get Started

• Step 2 - Create a memset() function to initialize the bitmask array with zeros. A bitmask of initial size L used to record the bitwise OR of strings in the strings arr[] array.

• Step 3 - To store the response, set the value of the maxLength variable to 0.

• Step 4 - Do the following while iterating over the range [0, L] using variable i -

• Step 5 - Define the value of bitmask[i] as mask[i]|1(arr[i][j] - 'a') and iterate over the range [0, S], where S is the size of the string.

• Step 6 - Use integer variable j to iterate over the range [0, i] and set the value of maxLength to the maximum value of arr[i].length() if bitmask[i] The result of bitwise AND with bitmask[j] is not 0, then arr[j].length().

• Step 7 - Finally print the obtained results.

• Step 8 - Stop

Example: C program

This is a C program implementation of the algorithm written above to maximize the sum of the lengths of a pair of strings with no characters in common in a given array

This is a C program implementation of the algorithm written above to maximize the sum of the lengths of a pair of strings with no characters in common in a given array

#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;
}

Output

7

in conclusion

Similarly, we can maximize the sum of the lengths of a pair of strings that have no common characters in the given array.

This article addresses the challenge of obtaining a program to maximize the sum of the lengths of a pair of strings that have no characters in common in a given array.

C programming code is provided here along with an algorithm to maximize the sum of the lengths of a pair of strings that have no characters in common in a given array.

The above is the detailed content of Given an array, find the maximum sum of the lengths of two strings that do not have the same characters.. For more information, please follow other related articles on the PHP Chinese website!