LeetCode — Decoded String at Index

Problem Link: https://leetcode.com/problems/decoded-string-at-index/

Problem Description: An encoded string S is given. To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken:

• If the character read is a letter, that letter is written onto the tape.
• If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total.

Now for some encoded string S, and an index K, find and return the K-th letter (1 indexed) in the decoded string.

Constraints:

• 2 <= S.length <= 100
• S will only contain lowercase letters and digits 2 through 9.
• S starts with a letter.
• 1 <= K <= 10^9
• It’s guaranteed that K is less than or equal to the length of the decoded string.
• The decoded string is guaranteed to have less than 2^63 letters.

Approach Used: Mathematical and String

Explanation: In general if a string s consist of a word w of length l_w repeated n times implying total length of s, l_s = l_w*n. If we want to find the kth letter in s, we can find (k % l_w)th character in l_w. For e.g., if s = “helloworldhelloworldhelloworld” then l_s = 30, as we can clearly see the repeated word so w = “helloworld” with l_w=10 and repeated n=3 times. This means that for e.g. finding 26th character in s is same as finding (26%10)th => 6th character in w, which will come to be ‘w’.

Using this logic we can find the Kth character without having to build the actual string. So for this first, we need to find the length of the complete string or l_s. For this, we will iterate through the input string and increase the size or l_s by 1 if we find an alphabet and multiply l_s by the digit if we encounter a digit.

Now once we get the total_length, we will use a reverse of logic explained above to get kth character. It is important to understand that in this case the whole string will not be exactly contained of one repeated string but several strings repeated in different frequencies. So we cannot simply do k%l_w and get it. We will have to constantly update our k and l_s based on the fact if the last character encountered is a digit or an alphabet.

Code: (Java)

public String decodeAtIndex(String S, int K) {
 
 //Note: this cannot be int as last constraint say that length of string can go up 2⁶³, but int can hold only till 2³¹
 long size_of_resultant_string=0;
 
 for(int i=0; i<S.length(); i++){
 if(Character.isDigit(S.charAt(i))==true){
 size_of_resultant_string*=(S.charAt(i)-’0');
 }
 else{
 size_of_resultant_string++;
 }
 }
 
 for(int i=S.length()-1; i>=0; i — ){
 // find new k for original string based on length of final string
 K%=size_of_resultant_string;
 
 //if k is 0 then we need to return this character itself. But only if it is not a number
 if(K==0 && Character.isAlphabetic(S.charAt(i)))
 return “”+S.charAt(i);
 
 //if k is not 0 and it is a characted then we reduce length of final string by 1
 if(Character.isAlphabetic(S.charAt(i)))
 size_of_resultant_string — ;
 
 //if k is not 0 and it is a digit then we reduce length of final string by 
 //number of characters added (reverse of logic to find length of resultant string) 
 else
 size_of_resultant_string/=(S.charAt(i)-’0');
 }
 return null;
 }

Complexity:

Space Complexity: O(1). Constant space used for size_of_resultant_string.

Time Complexity: O(n). Linear time as we only traverse all characters of string twice linearly.