替換字串中每個字元為其頻率 X 倍後的第 K 個字元

---

在這個問題中，我們給定一個字串 'str'、整數 K 和整數 X。該字串 'str' 僅包含 1 到 9 之間的整數。我們必須對字串執行恰好 X 次操作。操作是每次我們必須用它自身的頻率替換字串的一個字元。這裡的頻率是指字串字元的數量或值。我們的任務是在執行給定操作恰好 X 次後返回第 k 個字元。

示例

Input 1: str = “1231”, K = 5, X = 3

Output 1: 2

解釋

我們已經執行了 3 次操作，如給定。

1st time, str = 1223331 as 

• 對於字元 str[0]，頻率為 1，值為 1，所以 1 出現 1 次。

• 對於字元 str[1]，頻率為 2，值為 2，所以 2 出現 2 次。

• 其他字元也是如此。

2nd time, str = 122223333333331
3rd time, str = 1222222223333333333333333333333333331

因此，在恰好 X 次之後字串的第 K 個字元是 2。所以答案是 2。

Input 2: str = “1121”,  K = 2, X = 5 

Output 2: 2

我們已經看到了上面給定字串的示例，讓我們轉向方法 -

樸素方法

在這種方法中，我們透過執行給定操作來計算直到 X 次的新字串。在獲得恰好 X 次的字串後，我們返回該字串的第 K 個字元。

示例

讓我們看看程式碼以更好地理解上述方法 -

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Kth character of the string after X times
char findKthChar(string str, long long K, int X){
   string s = str; // create another string to store the give string as we need to update the string     
   for (int i = 0; i < X; i++) {
      string temp = ""; // To store the temporary result of each time
      for (int j = 0; j < s.size(); j++) {
         int freq = s[j] - '0'; // getting freq of char s[j]
         
         // adding char value its frequency times to 'temp' result.
         while (freq--) {  
            temp += s[j];
         }
      }
      s = temp; // update the string after.
   } 
   return s[K - 1]; // return Kth character of X times string
} 
int main(){

   // Given Input
   string str = "1231";
   long long K =  5;
   int X = 3;
   
   // Function Call
   char result = findKthChar(str, K, X);
   cout << result << "\n";
   return 0;
}

輸出

2

時間和空間複雜度

時間複雜度取決於給定的字串數字，並將等於數字的 x 次冪以及它們的總和。

空間複雜度與時間複雜度完全相同。

高效方法

這是上述方法的最佳化版本。其中我們計算每個字元的 X 次範圍，而不是每次都建立一個字串。

在這裡我們觀察到，每次字元都會根據字元值相對於時間的冪增加。

讓我們在下面討論上述方法的主要步驟 -

• 建立 kthChar 變數以儲存 x 次字串的第 kthChar

• 建立變數 tot 以儲存 X 次後每個字元出現的次數

• 使用 for 迴圈遍歷字串並執行以下步驟

−>獲取當前字元的值

−>使用該值和 X，我們得到 X 次後該當前字元的範圍。正如我們觀察到的，每次字元都會增加到值的冪 X

作為 pow(value, X)。

−>將該範圍儲存在變數 'tot' 中以維護 X 次後字串的長度

−>檢查第 K 個字元是否位於 X 次後字串的當前長度中

作為 (K <= tot) 如果是，則中斷 for 迴圈並將當前字元儲存到變數 'kthChar' 中

• 返回 kthChar

示例

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Kth character of the string after X times
char findKthChar(string str, long long K, int X){
   char kthChar; // Variable to store the KthChar of x times string
   int tot = 0; // to store the count of the each character occur after the X times 
   
   // Traverse the string 'str'
   for (int i = 0; i < str.size(); i++) { 
      int value = str[i] - '0'; // Convert char into int to get the value 
      
      // Calculate each characters occuring range
      int charRange = pow(value, X);
      tot += charRange; 
      
      // If K is less than tot than kthChar is str[i]
      if (K <= tot) {
         kthChar = str[i];
         break; // break the for loop
      }
   }
   
   // Return answer, kthChar of the string after X times
   return kthChar;
}
int main(){
   string str = "1231"; // given string
   long long K =  5; // given integer
   int X = 3; // given integer
   
   // Function Call to get the kth character after X times
   char result = findKthChar(str, K, X); 
   
   // Print the result
   cout << result << "\n";
   return 0;
}

輸出

2

時間和空間複雜度

上述程式碼的時間複雜度為 O(N)，其中 N 是給定長度的大小。

上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。

結論

在本教程中，我們實現了一個程式，用於查詢在將字串的每個字元替換為其頻率恰好 X 次後的第 K 個字元。我們實現了兩種方法，一種是樸素方法，另一種是高效方法。