Find K-th Character of Decrypted String in C++ - Set 2

Concept

With respect of a given encoded string where repetitions of substrings are indicated as substring followed by count of substrings. So, for example, if encrypted string is “pq2rs2” and k=5, so output will be ‘r’ because decrypted string is “pqpqrsrs” and 5th character is ‘r’.

It should be noted that frequency of encrypted substring can be of more than one digit. So, for example, in “pq12r3”, pq is repeated 12 times. Here, no leading 0 is present in frequency of substring.

Input

"p2q2r3", k = 6

Output

r

Decrypted string is "ppqqrrr"

Input

"pq4r2ts3", k = 11

Output

t

Decrypted string is "pqpqpqpqrrtststs"

Method

Here, the stepwise algorithm is −

• Determine length of current substring. Implement two pointers. We have to fix one pointer at starting of substring and proceed another pointer until a digit is not found.
• Determine frequency of repetition by moving the second pointer further until an alphabet is not found.
• Determine length of substring if it is repeated by multiplying frequency and its original length.

• It has been observed that if this length is smaller than k, then required character lies in substring that follows. We have to subtract this length from k to maintain count of number of characters that are required to be covered.

• It has been seen that if length is smaller than or equal to k, then required character lies in current substring. Because k is 1-indexed, decrease it by 1 and then take its mod with original substring length. Here, required character is kth character from beginning of substring which is pointed by first pointer.

Example

 Live Demo

// C++ program to find K'th character in
// decrypted string
#include <bits/stdc++.h>
using namespace std;
// Shows function to find K'th character in
// Encoded String
char encodedChar(string str, int k){
   int a, b;
   int m = str.length();
   // Used to store length of substring
   int len1;
   // Used to store length of substring when
   // it is repeated
   int num1;
   // Used to store frequency of substring
   int freq1;
   a = 0;
   while (a < m) {
      b = a;
      len1 = 0;
      freq1 = 0;
      // Determine length of substring by
      // traversing the string until
      // no digit is found.
      while (b < m && isalpha(str[b])) {
      b++;
      len1++;
   }
   // Determine frequency of preceding substring.
   while (b < m && isdigit(str[b])) {
      freq1 = freq1 * 10 + (str[b] - '0');
      b++;
   }
   // Determine length of substring when
   // it is repeated.
   num1 = freq1 * len1;
   // It has been seen that if length of repeated substring is
   less than // k then required character is present in next
   // substring. Subtract length of repeated
   // substring from k to keep account of number of
   // characters required to be visited.
   if (k > num1) {
      k -= num1;
      a = b;
   }
   // It has been seen that if length of repeated substring is
   // more or equal to k then required
   // character lies in current substring.
      else {
         k--;
         k %= len1;
         return str[a + k];
      }
   }
   // This is for the case when there
   // are no repetition in string.
   // e.g. str="abced".
   return str[k - 1];
}
// Driver Code
int main(){
   string str1 = "pqpqpqpqrrtststs";
   int k1 = 11;
   cout << encodedChar(str1, k1) << endl;
   string str2 = "p2q2r3";
   int k2 = 6;
   cout << encodedChar(str2, k2) << endl;
   return 0;
}

Output

t
r