Find K’th Character of Decrypted String
You have been given an Encrypted String where repetitions of substrings are represented as substring followed by the count of substrings.

Example: String "aabbbcdcdcd" will be encrypted as "a2b3cd3".

You need to find the 'K'th character of Decrypted String. Decrypted String would have 1-based indexing.

Note :

Input string will always be lowercase characters without any spaces. If the count of a substring is 1 then also it will be followed by Integer '1'. Example: "aabcdee" will be Encrypted as "a2bcd1e2" This means it's guaranteed that each substring is followed by some Integer. Also, the 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 the frequency of substring. The frequency of a repeated substring can also be in parts. Example: "aaaabbbb" can also have "a2a2b3b1" as Encrypted String.

Input format :

The first line of each test case contains an Encrypted String 'S'. The second line contains the integer value 'K'.

Output format :

For each test case print, the 'K'th character of Decrypted String obtained from Encrypted String 'S'.

Note :

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints :

2

Question

Find K’th Character of Decrypted String

You have been given an Encrypted String where repetitions of substrings are represented as substring followed by the count of substrings.

Example: String "aabbbcdcdcd" will be encrypted as "a2b3cd3".

You need to find the 'K'th character of Decrypted String. Decrypted String would have 1-based indexing.

Note :

Input string will always be lowercase characters without any spaces.

If the count of a substring is 1 then also it will be followed by Integer '1'.
Example: "aabcdee" will be Encrypted as "a2bcd1e2"
This means it's guaranteed that each substring is followed by some Integer.

Also, the 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 the frequency of substring.

The frequency of a repeated substring can also be in parts.
Example: "aaaabbbb" can also have "a2a2b3b1" as Encrypted String.

Input format :

The first line of each test case contains an Encrypted String 'S'. 

The second line contains the integer value 'K'.

Output format :

For each test case print, the 'K'th character of Decrypted String obtained from Encrypted String 'S'.

Note :

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints :

2 <= N <= 10^5
1 <= K <= M
1 <= M <= 10^18

Where 'N' is the length of String 'S' and 'M' is the length of the Decrypted String of 'S'. 
All the characters of String 'S' are lowercase English letters.

Time Limit: 1sec

Accepted Answer

I was able to pass all test cases

Accepted Answer

Decryption

We will just iterate through Encrypted String ‘S’ and will create a Decrypted String. Then we can print the K’th character of Decrypted String.

We will find the substring by traversing the string until no digit is found.
Then find the frequency of the preceding substring by traversing the string until no lowercase alphabet is found. We can use this relation to create the Integer frequency from the string:
- freqOfSubstring = freqOfSubstring * 10 + (S[j] - '0');
We will append the substring ‘freqOfSubstring’ times in Decrypted String.
We will keep repeating the above process until the whole string ‘S’ is traversed.
Finally, we have our decrypted string, print the (K-1)’th index of Decrypted String.

Space Complexity: OtherExplanation:

O(M), where ‘M' is the length of the Decrypted String of Encrypted String 'S'.

As we are creating the Decrypted String.

Time Complexity: OtherExplanation:

O(M), where ‘M' is the length of the Decrypted String of Encrypted String 'S'.

As we are creating Decrypted String, we will append the number of characters in the Decrypted String.

Accepted Answer

Without Decryption

We will just iterate through Encrypted String ‘S’ and will keep a track on length passed in Decrypted String.

We will find the length of the substring (‘substringLength’) by traversing the string until no digit is found.
Then find the frequency of the preceding substring by traversing the string until no lowercase alphabet is found. We can use this relation to create the Integer frequency from the string:
- freqOfSubstring = freqOfSubstring * 10 + (S[j] - '0').
Find the length of the resultant string in the Decrypted string.
- resultantLength = freqOfSubstring * substringLength.
If the resultantLength of the repeated substring is less than 'K' then required character is present in some later substring. Subtract the resultantLength of repeated substring from 'K' to keep account of the number of characters required to be visited.
- K = K - resultantLength
If the length of repeated substring is more or equal to 'K' then required character lies in the current substring.
- return the (K-1)%substringLength character from current substring
We will keep repeating the above process until we have reached our K’th character.

Space Complexity: O(1)Explanation:

O(1)

As we are not creating any Decrypted String and just keeping the length of string and substring in constant space.

Time Complexity: O(n)Explanation:

O(N), where 'N' is the length of Encrypted String 'S'.

As we are only traversing through Encrypted String 'S'.

You have been given an Encrypted String where repetitions of substrings are represented as substring followed by the count of substrings.

You need to find the 'K'th character of Decrypted String. Decrypted String would have 1-based indexing.

Note :

Input format :

Output format :

Note :

Constraints :

Top HashedIn by Deloitte Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in HashedIn by Deloitte Software Developer