替换字符串中每个字符为其频率 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 个字符。我们实现了两种方法，一种是朴素方法，另一种是高效方法。