Find k-th character of decrypted string | Set – 2
Last Updated :
21 Apr, 2021
Given an encoded string where repetitions of substrings are represented as substring followed by count of substrings. For example, if encrypted string is “ab2cd2” and k=4, so output will be ‘b’ because decrypted string is “ababcdcd” and 4th character is ‘b’.
Note: Frequency of encrypted substring can be of more than one digit. For example, in “ab12c3”, ab is repeated 12 times. No leading 0 is present in frequency of substring.
Examples:
Input: "a2b2c3", k = 5
Output: c
Decrypted string is "aabbccc"
Input: "ab4c2ed3", k = 9
Output : c
Decrypted string is "ababababccededed"
The solution discussed in previous post requires additional O(n) space. The following post discuss a solution that requires constant space. The stepwise algorithm is:
- Find length of current substring. Use two pointers. Fix one pointer at beginning of substring and move another pointer until a digit is not found.
- Find frequency of repetition by moving the second pointer further until an alphabet is not found.
- Find length of substring if it is repeated by multiplying frequency and its original length.
- If this length is less than k, then required character lies in substring that follows. Subtract this length from k to keep count of number of characters that are required to be covered.
- If length is less than or equal to k, then required character lies in current substring. As k is 1-indexed reduce it by 1 and then take its mod with original substring length. Required character is kth character from starting of substring which is pointed by first pointer.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
char encodedChar(string str, int k)
{
int i, j;
int n = str.length();
int len;
int num;
int freq;
i = 0;
while (i < n) {
j = i;
len = 0;
freq = 0;
while (j < n && isalpha(str[j])) {
j++;
len++;
}
while (j < n && isdigit(str[j])) {
freq = freq * 10 + (str[j] - '0');
j++;
}
num = freq * len;
if (k > num) {
k -= num;
i = j;
}
else {
k--;
k %= len;
return str[i + k];
}
}
return str[k - 1];
}
int main()
{
string str = "abced";
int k = 4;
cout << encodedChar(str, k) << endl;
return 0;
}
|
Java
import java.util.*;
class GFG
{
static char encodedChar(char[] str, int k)
{
int i, j;
int n = str.length;
int len;
int num;
int freq;
i = 0;
while (i < n)
{
j = i;
len = 0;
freq = 0;
while (j < n && Character.isAlphabetic(str[j]))
{
j++;
len++;
}
while (j < n && Character.isDigit(str[j]))
{
freq = freq * 10 + (str[j] - '0');
j++;
}
num = freq * len;
if (k > num)
{
k -= num;
i = j;
}
else
{
k--;
k %= len;
return str[i + k];
}
}
return str[k - 1];
}
public static void main(String[] args)
{
String str = "abced";
int k = 4;
System.out.println(encodedChar(str.toCharArray(), k));
}
}
|
Python3
def encodedChar(string, k):
n = len(string)
i = 0
while i < n:
j = i
length = 0
freq = 0
while j < n and string[j].isalpha():
j += 1
length += 1
while j < n and string[j].isdigit():
freq = freq * 10 + int(string[j])
j += 1
num = freq * length
if k > num:
k -= num
i = j
else:
k -= 1
k %= length
return string[i + k]
return string[k - 1]
if __name__ == "__main__":
string = "abced"
k = 4
print(encodedChar(string, k))
|
C#
using System;
class GFG
{
static char encodedChar(char[] str, int k)
{
int i, j;
int n = str.Length;
int len;
int num;
int freq;
i = 0;
while (i < n)
{
j = i;
len = 0;
freq = 0;
while (j < n && char.IsLetter(str[j]))
{
j++;
len++;
}
while (j < n && char.IsDigit(str[j]))
{
freq = freq * 10 + (str[j] - '0');
j++;
}
num = freq * len;
if (k > num)
{
k -= num;
i = j;
}
else
{
k--;
k %= len;
return str[i + k];
}
}
return str[k - 1];
}
public static void Main(String[] args)
{
String str = "abced";
int k = 4;
Console.WriteLine(encodedChar(str.ToCharArray(), k));
}
}
|
Javascript
<script>
function encodedChar(str, k)
{
var i, j;
var n = str.length;
var len;
var num;
var freq;
i = 0;
while (i < n)
{
j = i;
len = 0;
freq = 0;
while (j < n && str[j].match(/^[0-9a-z]+$/))
{
j++;
len++;
}
while (j < n && str[j].match(/^[0-9]+$/))
{
freq = freq * 10 + (str[j] - '0');
j++;
}
num = freq * len;
if (k > num)
{
k -= num;
i = j;
}
else
{
k--;
k %= len;
return str[i + k];
}
}
return str[k - 1];
}
var str = "abced";
var k = 4;
document.write(encodedChar(str, k));
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)