最小化所需操作的次數，使得兩個給定的字串成為彼此的排列

在本文中，我們將討論如何最大限度地減少兩個給定字串相互排列所需的給定操作的數量。我們將遵循逐步方法並提供 C 程式碼實作。我們還將提供一個範例測試案例來幫助理解問題和解決方案。

問題陳述

給定兩個字串 s1 和 s2，我們需要找到使 s1 和 s2 彼此排列所需的最少運算元。我們可以執行兩種操作：交換 s1 的任兩個字符，或是交換 s2 的任兩個字符。

方法與實作

為了解決這個問題，我們需要統計兩個字串中不存在的字元的數量，即兩個字串中字元出現頻率的差異。使兩個字串彼此排列所需的最小交換次數等於此計數的一半，因為我們可以交換任一字串中的字元以使它們相等。

首先，我們將使用兩個陣列來計算兩個字串中字元的頻率。然後，我們將迭代兩個陣列並將字元頻率之間的絕對差加到變數中。該變數將儲存兩個字串中都不存在的字元數。

計算完計數後，我們將傳回其中的一半作為兩個字串相互排列所需的最小交換次數。

範例

下面是上述方法的 C 程式碼實作 -

#include<bits/stdc++.h>
using namespace std;

int countMinSwaps(string s1, string s2) {
   int freq1[26] = {0}, freq2[26] = {0}, count = 0;
   for (char c : s1) {
      freq1[c - 'a']++;
   }
   for (char c : s2) {
      freq2[c - 'a']++;
   }
   for (int i = 0; i < 26; i++) {
      count += abs(freq1[i] - freq2[i]);
   }
   return count / 2;
}

int main() {
   string s1 = "hello";
   string s2 = "world";
   int minSwaps = countMinSwaps(s1, s2);
   cout << "Minimum number of swaps required: " << minSwaps << endl;
   return 0;
}

輸出

Minimum number of swaps required: 3

範例測試案例

讓我們考慮此測試案例的範例字串「hello」和「world」。

兩個字串的頻率數組如下 -

freq1 = {0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
freq2 = {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}

我們可以看到，字元「l」在 s1 中出現的頻率為 2，但在 s2 中只有 1，而字元「r」在 s2 中出現的頻率為 1，但在 s1 中不存在。因此，兩個字串中都不存在的字元數為 3。

因此，兩個字串相互排列所需的最少交換次數為 1。我們可以將 s1 中的“l”與 s2 中的“r”交換，得到字串“herlo”和“wolld”，它們是彼此的排列。

結論

在本文中，我們討論瞭如何最大限度地減少兩個給定字串相互排列所需的給定操作的數量。我們遵循逐步方法並提供了 C 程式碼實作。我們還提供了一個範例測試案例來幫助理解問題和解決方案。此問題可以以 O(n) 時間複雜度和 O(1) 空間複雜度解決。

以上是最小化所需操作的次數，使得兩個給定的字串成為彼此的排列的詳細內容。更多資訊請關注PHP中文網其他相關文章！