從給定陣列中找出字元不重複的兩字串，使其長度之和最大

---

本文旨在實現一個程式，從給定陣列中找出字元不重複的兩字串，使其長度之和最大。根據定義，字串是字元的集合。

問題陳述

實現一個程式，從給定陣列中找出字元不重複的兩字串，使其長度之和最大。

示例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 語言程式碼以及從給定陣列中找出字元不重複的兩字串，使其長度之和最大的演算法。