Decoded String At Index - Leetcode Solution

Problem Statement:

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 performed:

• 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.

The tape consists of the current decoded and written characters (from step 1.). Return the kth letter (1 indexed) in the decoded string.

Example: Input: s = "leet2code3", k = 10 Output: "o" Explanation: The decoded string is "leetleetcodeleetleetcodeleetleetcode". The 10th letter in the string is "o".

Solution:

Approach: We can decode the given encoded string in reverse order as it will help us to maintain the decoded string so far and the factor (how many times the current string is repeated). We can start decoding the string from the last character and calculate how many times the current string is repeated and include only the necessary portion of the string which contains the kth index.

Algorithm:

• Initialize a pointer to traverse the decoded string in reverse order.

• Traverse in reverse order through the given encoded string from right to left.

• If the current character being traversed is not a digit:

• Decrement the value of k.

• If value of k becomes 0, the function returns the current character.

• If the current character being traversed is a digit:

• Update n to the value of the digit.

• Update the value of currentFactor by discarding the currentFactor/n.

• Decrement the value of k by the factor.

• CurrentFactor will contain the number of times the previous string is repeated, so if k is less than currentFactor and greater than 0, set the pointer value to '-1' (signifying that the previous character is yet to be evaluated).

• If k is zero, then return the current character.

• Continue the loop and update the value of k.

Time Complexity: O(n) Space Complexity: O(1)

Code:

class Solution { public: string decodeAtIndex(string s, int k) { long currentFactor = 1; int n = s.size(); for(int i = 0; i < n; i++) { char current = s[i]; if(isdigit(current)) { currentFactor *= current-'0'; } else { if(currentFactor >= k) { k--; if(k == 0) return string(1,current); currentFactor /= (current-'a'+1); continue; } else { k -= currentFactor; if(k == 0) return string(1,current); } } } return ""; } };

This code allocates constant amount of memory and processes the input string from right to left using a while loop.

1