Replace each character in a string with the Kth character after its frequency exactly X times

In this problem, we are given a string "str", an integer K and an integer X. The string "str" ​​contains only integers between 1 and 9. We have to perform X operations on this string. The operation is that each time we have to replace the number of occurrences of a character in the string with a character in the string. The frequency here refers to the number or value of characters in the string. Our task is to return the k-th character after performing a given operation X times.

Example

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

Output 1: 2

illustrate

We have performed the given operation 3 times.

1st time, str = 1223331 as 

• For the character str[0], the frequency is 1 and the value is 1, so 1 appears 1 time.

• For the character str[1], the frequency is 2 and the value is 2, so 2 appears 2 times.

• Other characters are similar.

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

So the Kth character of the string exactly X times later is 2. So the answer is 2.

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

Output 2: 2

We have seen the example of the given string above, let us move to the method -

Naive method

In this method, we calculate the new string by performing the given operation until X times. After getting the string exactly X times, we return the Kth character of the string.

Example

Let’s take a look at the code to better understand the above method -

#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;
}

Output

2

Time and space complexity

The time complexity depends on the given string numbers and is equal to the x power of the number and the sum of each number.

Space complexity is exactly the same as time complexity.

Efficient method

It is an optimized version of the above method. where we calculate the range for each charter X times instead of creating a string each time.

Here we observe that each time the character is increased by the power of time relative to the character value.

Let us discuss the main steps of the above method below -

• Create kthChar variable to store the KthChar of x times string

• Create variable tot to store the count of occurrences of each character after X times

• Use a for loop to iterate through the string and perform the following steps

->Get the value of the current character

->Using this value and X, we can get the range of the current character after X times. As we can observe, the character's strength value increases by X

each time

As pow(value, X).

−> Store the range in the variable "tot" to maintain the length of the string after X times

−> Check whether the Kth character after X times is within the current length of the string

As (K

• Return kthChar

Example

#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;
}

Output

2

Time and space complexity

The time complexity of the above code is O(N), where N is the size of the given length.

The space complexity of the above code is O(1) because we are not using any extra space.

in conclusion

In this tutorial, we implemented a program that finds the Kth character in a String after replacing each character with its frequency exactly X times. We implemented two methods, one is the naive method and the other is the effective method.

The above is the detailed content of Replace each character in a string with the Kth character after its frequency exactly X times. For more information, please follow other related articles on the PHP Chinese website!