將一個字串轉換為另一個給定字串所需的最小增量為 1 或 K

---

我們給出了兩個字串，需要透過點選增量將一個字串轉換為另一個字串，並且我們可以在單個操作中將字元增量 1 或 k。

為了解決這個問題，我們需要透過執行迴圈增量操作，使第一個字串的所有字元與第二個字元相同。如果兩個字串中相同索引處的字元相同，則我們不需要執行任何增量操作。

問題陳述 – 我們給出了兩個名為 first 和 second 的字串，包含大寫字母字元。兩個字串的長度均為 N。此外，我們還給出了正整數 K，表示我們可以在單個操作中將字元增量 1 或 k。我們需要找到將字串從 first 轉換為 second 的迴圈增量的總數。

示例

輸入– first = "ACSQ", second = "BCOS", k = 7

輸出– 7

解釋

• 要將 A 轉換為 B，我們需要 1 個增量操作。

• 要將 C 轉換為 C，我們需要執行 0 個操作。

• 要將 S 轉換為 O，我們需要總共 22 個迴圈增量。我們可以執行 7 個增量的 (k = 3) 個操作和 1 個增量的 1 個操作。我們需要總共 4 個操作。

• 要將 Q 轉換為 S，我們需要 2 個增量。因此，所需的總運算元為 2，因為我們需要將 Q -> R 和 R -> S 轉換。

• 所需的總運算元為 1 + 0 + 4 + 2 = 7。

輸入– first = "ACSQ", second = "BCOS", K = 9

輸出– 0

解釋 – 我們不需要執行任何增量操作，因為兩個字串的所有字元都相同。

輸入– first = "AB", second = "FG", K = 6

輸出– 6

解釋 –

• 要將 A 轉換為 F，我們需要 5 個增量。因此，我們可以執行 3 個增量的 1 個操作和 1 個增量的 2 個操作。我們需要總共 3 個操作。

• 要將 B 轉換為 G，我們需要 5 個增量。因此，我們需要執行 3 個操作。

• 我們需要總共 6 個操作。

方法 1

在這種方法中，我們將遍歷字串。之後，我們將找到字元之間的迴圈差異。我們可以透過將差異除以 K 來獲得 K 的總增量數，並透過執行不同與 K 的模運算來獲得 1 的總增量數。

演算法

• 將“total”變數初始化為零以儲存運算元。

• 使用迴圈遍歷字串。

• 如果 first 和 second 字串在第 i 個索引處具有相同的字元，則使用“continue”關鍵字移動到下一個迭代，因為我們不需要執行任何操作。

• 如果 first 字串的字元小於 second 字串在第 i 個索引處的字元，請執行以下步驟。

• 如果 second[i] - first[i] 大於 K，則將 (second[i] - first[i]) / K 新增到最初為零的“cnt”變數。它為我們提供了我們可以透過將字元增加 K 來執行的操作總數。

• 將 (second[i] - first[i]) % K 新增到“cnt”，表示 1 所需的總增量數。

• 如果 first 字串的字元大於 second 字串在第 i 個索引處的字元，請執行以下步驟。

• 獲取差異 (first[i] - second[i])，從中減去 26，並將結果儲存到“temp”變數中。

• 如果 temp 大於 K，則將 temp / K 新增到“cnt”變數中。

• 將 temp % K 新增到“cnt”變數中。

• 當一個迴圈迭代完成後，將“cnt”值新增到“total”。

• 返回“total”值。

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the total minimum operations required to convert the string first to second with the given condition
int totalOperations(string first, string second, int K){
   // to store the count of operations
   int total = 0;
   // Traverse the string first
   for (int i = 0; i < first.length(); i++){
      // to store the total operations required to convert the current character of first to second
      int cnt = 0;
      // If the characters are the same, then continue
      if (first[i] == second[i])
          continue;
      // If the character of first is less than the character of second
      else if (first[i] < second[i]){
          // If the difference is greater than K
          if ((second[i] - first[i]) >= K){
              // Add the difference/K to cnt
              cnt = (second[i] - first[i]) / K;
          }
          // Add the difference%K to the cnt
          cnt += (second[i] - first[i]) % K;
      }
      // If the character of first is greater than the character of second
      else{
          int temp = 26 - (first[i] - second[i]);
          // Add the difference/K to cnt
          if (temp >= K)
              cnt = temp / K;
          // Add the difference%K to the cnt
          cnt += (temp % K);
      }
      total += cnt;
   }
   return total;
}
int main(){
   string first = "ACSQ", second = "BCOS";
   int K = 7;
   cout << "The total number of minimum operations require to convert the first string to second are " << totalOperations(first, second, K);
}

輸出

The total number of minimum operations require to convert the first string to second are 7

時間複雜度 – O(N)，因為我們將 first 字串的所有字元轉換為 second 字串。

空間複雜度 – O(1)，因為我們不使用任何常數空間。

在這個問題中，我們透過執行迴圈增量操作將 first 字串轉換為 second 字串。程式設計師可以嘗試解決需要執行迴圈減量操作總數才能將 first 字串轉換為 second 字串的問題。