Dada una string codificada donde las repeticiones de substrings se representan como substrings seguidas por el recuento de substrings. Por ejemplo, si la string cifrada es «ab2cd2» y k=4, la salida será ‘b’ porque la string descifrada es «ababcdcd» y el cuarto carácter es ‘b’.
Nota: La frecuencia de la substring cifrada puede tener más de un dígito. Por ejemplo, en “ab12c3”, ab se repite 12 veces. Ningún 0 inicial está presente en la frecuencia de la substring.
Ejemplos:
C++
// C++ program to find K'th character in
// decrypted string
#include <bits/stdc++.h>
using namespace std;
// Function to find K'th character in
// Encoded String
char encodedChar(string str, int k)
{
int i, j;
int n = str.length();
// To store length of substring
int len;
// To store length of substring when
// it is repeated
int num;
// To store frequency of substring
int freq;
i = 0;
while (i < n) {
j = i;
len = 0;
freq = 0;
// Find length of substring by
// traversing the string until
// no digit is found.
while (j < n && isalpha(str[j])) {
j++;
len++;
}
// Find frequency of preceding substring.
while (j < n && isdigit(str[j])) {
freq = freq * 10 + (str[j] - '0');
j++;
}
// Find length of substring when
// it is repeated.
num = freq * len;
// 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 > num) {
k -= num;
i = j;
}
// If length of repeated substring is
// more or equal to k then required
// character lies in current substring.
else {
k--;
k %= len;
return str[i + 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 str = "abced";
int k = 4;
cout << encodedChar(str, k) << endl;
return 0;
}
Java
// Java program to find K'th character in
// decrypted string
import java.util.*;
class GFG
{
// Function to find K'th character in
// Encoded String
static char encodedChar(char[] str, int k)
{
int i, j;
int n = str.length;
// To store length of substring
int len;
// To store length of substring when
// it is repeated
int num;
// To store frequency of substring
int freq;
i = 0;
while (i < n)
{
j = i;
len = 0;
freq = 0;
// Find length of substring by
// traversing the string until
// no digit is found.
while (j < n && Character.isAlphabetic(str[j]))
{
j++;
len++;
}
// Find frequency of preceding substring.
while (j < n && Character.isDigit(str[j]))
{
freq = freq * 10 + (str[j] - '0');
j++;
}
// Find length of substring when
// it is repeated.
num = freq * len;
// 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 > num)
{
k -= num;
i = j;
}
// If length of repeated substring is
// more or equal to k then required
// character lies in current substring.
else
{
k--;
k %= len;
return str[i + k];
}
}
// This is for the case when there
// are no repetition in string.
// e.g. str="abced".
return str[k - 1];
}
// Driver Code
public static void main(String[] args)
{
String str = "abced";
int k = 4;
System.out.println(encodedChar(str.toCharArray(), k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find K'th # character in decrypted string # Function to find K'th character # in Encoded String def encodedChar(string, k): n = len(string) i = 0 while i < n: j = i length = 0 freq = 0 # Find length of substring by # traversing the string until # no digit is found. while j < n and string[j].isalpha(): j += 1 length += 1 # Find frequency of preceding substring. while j < n and string[j].isdigit(): freq = freq * 10 + int(string[j]) j += 1 # Find the length of the substring # when it is repeated. num = freq * length # If the length of the repeated substring # is less than k then required character # is present in next substring. Subtract # the length of repeated substring from # k to keep account of the number # of characters required to be visited. if k > num: k -= num i = j # If length of repeated substring is # more or equal to k then required # character lies in current substring. else: k -= 1 k %= length return string[i + k] # This is for the case when there are no # repetition in string. e.g. str="abced". return string[k - 1] # Driver Code if __name__ == "__main__": string = "abced" k = 4 print(encodedChar(string, k)) # This code is contributed # by Rituraj Jain
C#
// C# program to find K'th character in
// decrypted string
using System;
class GFG
{
// Function to find K'th character in
// Encoded String
static char encodedChar(char[] str, int k)
{
int i, j;
int n = str.Length;
// To store length of substring
int len;
// To store length of substring when
// it is repeated
int num;
// To store frequency of substring
int freq;
i = 0;
while (i < n)
{
j = i;
len = 0;
freq = 0;
// Find length of substring by
// traversing the string until
// no digit is found.
while (j < n && char.IsLetter(str[j]))
{
j++;
len++;
}
// Find frequency of preceding substring.
while (j < n && char.IsDigit(str[j]))
{
freq = freq * 10 + (str[j] - '0');
j++;
}
// Find length of substring when
// it is repeated.
num = freq * len;
// 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 > num)
{
k -= num;
i = j;
}
// If length of repeated substring is
// more or equal to k then required
// character lies in current substring.
else
{
k--;
k %= len;
return str[i + k];
}
}
// This is for the case when there
// are no repetition in string.
// e.g. str="abced".
return str[k - 1];
}
// Driver Code
public static void Main(String[] args)
{
String str = "abced";
int k = 4;
Console.WriteLine(encodedChar(str.ToCharArray(), k));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find K'th character in
// decrypted string
// Function to find K'th character in
// Encoded String
function encodedChar(str, k)
{
var i, j;
var n = str.length;
// To store length of substring
var len;
// To store length of substring when
// it is repeated
var num;
// To store frequency of substring
var freq;
i = 0;
while (i < n)
{
j = i;
len = 0;
freq = 0;
// Find length of substring by
// traversing the string until
// no digit is found.
while (j < n && str[j].match(/^[0-9a-z]+$/))
{
j++;
len++;
}
// Find frequency of preceding substring.
while (j < n && str[j].match(/^[0-9]+$/))
{
freq = freq * 10 + (str[j] - '0');
j++;
}
// Find length of substring when
// it is repeated.
num = freq * len;
// 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 > num)
{
k -= num;
i = j;
}
// If length of repeated substring is
// more or equal to k then required
// character lies in current substring.
else
{
k--;
k %= len;
return str[i + k];
}
}
// This is for the case when there
// are no repetition in string.
// e.g. str="abced".
return str[k - 1];
}
// Driver Code
var str = "abced";
var k = 4;
document.write(encodedChar(str, k));
// This code is contributed by rutvik_56
</script>