C++ 给定数组中没有共同字符的一对字符串的长度之和的最大值

本文的目的是实现一个程序，用于将给定数组中没有共同字符的一对字符串的长度之和最大化。根据定义，字符串是字符的集合。

问题陈述

实现一个程序，用于将给定数组中没有共同字符的一对字符串的长度之和最大化。

示例1

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

Output obtained: 8

解释

字符串“abcd”和“wxyz”中没有共同的字符。因此，两个字符串的长度之和为4 + 4，等于8，是所有可行对中最长的长度。

示例2

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

Output obtained: 7

解释

字符串 “abcd” 和 “hij” 没有共同的字符。因此，两个字符串的长度相加为4 + 3，等于8，是所有可行对中最长的长度。

示例3

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

Output obtained: 9

解释

字符串 “abcdx” 和 “lmno” 中没有相同的字符。因此，两个字符串的长度相加为 5 + 4，等于 9，这是所有可行配对中的最长长度。

示例4

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

Output obtained: 7

解释

字符串”coat”和”hij”没有共同的字符。因此，两个字符串的长度相加为4 + 3，等于8，是所有可行配对中最长的长度。

解决方案

为了使一个给定数组中没有共同字符的一对字符串的长度之和最大化，我们采取以下方法。

解决这个问题或找到一对没有共同字符的字符串长度之和最大的解决方案的方法如下。即，处理上述问题最直接的方法是创建字符串数组的每个可能配对，并显示没有共同字符的所有可能配对的字符串长度之和的最大值。

利用位运算的概念，上述策略也可以改进。这里的目标是在确定没有共同字符且长度最长的字符串对之前，将每个字符串转换为它们的位掩码整数等效形式。

位掩码是我们的主题。什么是位掩码?

我们首先要记住整数是什么。整数只是一系列位按顺序排列。位掩码的概念是使用其二进制形式以图形方式表示一个数字。

简而言之，”Bitmask”是一个指定任意东西的二进制数。

步骤

实现一个程序，从给定数组中找到没有共同字符的一对字符串的长度之和最大的算法如下所示:

第1步 - 开始
第2步 - 创建memset()函数，将位掩码数组初始化为零。位掩码的初始大小为L，以记录字符串数组arr[]中的字符串的按位或结果。
第3步 - 将maxLength变量的值设为0，以存储结果。
第4步 - 在使用变量i遍历范围[0, L]时执行以下操作-
第5步 - 将bitmask[i]的值定义为mask[i]|1(arr[i][j] – ‘a’)，并在范围[0, S]上进行迭代，其中S是字符串的长度。
第6步 - 使用整数变量j在范围[0, i]上进行迭代，并且如果bitmask[i]和bitmask[j]的按位与结果不为0，则将maxLength的值设为arr[i].length() + arr[j].length()的最大值。
第7步 - 在最后打印得到的结果。
第8步 - 停止

示例: C程序

这里是上述算法的C程序实现，用于从给定数组中找到一对没有公共字符的字符串，使其长度之和最大。

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