从给定数组中找出字符不重复的两字符串，使其长度之和最大

---

本文旨在实现一个程序，从给定数组中找出字符不重复的两字符串，使其长度之和最大。根据定义，字符串是字符的集合。

问题陈述

实现一个程序，从给定数组中找出字符不重复的两字符串，使其长度之和最大。

示例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 = 7，这是所有可能的组合中最大的长度。

示例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 = 7，这是所有可能的组合中最大的长度。

解决方案方法

为了从给定数组中找出字符不重复的两字符串，使其长度之和最大，我们采用以下方法。

解决这个问题或找到从给定数组中找出字符不重复的两字符串，使其长度之和最大的方法如下。最直接的方法是生成字符串数组的所有可能的配对，然后显示所有可能的、没有公共字符的配对中字符串长度之和的最大值。

使用位操作的概念，可以改进上述策略。这里的目标是在识别没有公共字符且长度和尽可能大的字符串对之前，将每个字符串转换为其位掩码整数等价物。

位掩码正是我们现在要讨论的主题。位掩码究竟是什么？

我们首先回顾一下整数是什么。整数只是一串连接在一起的位。位掩码的概念是用其二进制形式图形化地表示一个数字。

简单地说，“位掩码”是一个指定任何事物的二进制数。

算法

下面给出了从给定数组中找出字符不重复的两字符串，使其长度之和最大的程序的算法。

• 步骤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 语言程序实现，用于从给定数组中找出字符不重复的两字符串，使其长度之和最大

以下是上述算法的 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;
}

输出

7

结论

同样，我们可以从给定数组中找出字符不重复的两字符串，使其长度之和最大。

本文解决了从给定数组中找出字符不重复的两字符串，使其长度之和最大的程序的挑战。

这里提供了 C 语言代码以及从给定数组中找出字符不重复的两字符串，使其长度之和最大的算法。