Problem

You are given an encoded string s. To decode the 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 d, the entire current tape is repeatedly written d - 1 more times in total.

Given an integer k, return the kth letter (1-indexed) in the decoded string.

Examples

Example 1:

1
2
3
4

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

Example 2:

1
2
3
4

Input: s = "ha22", k = 5
Output: "h"
Explanation: The decoded string is "hahahaha".
The 5th letter is "h".

Example 3:

1
2
3
4

Input: s = "a2345678999999999999999", k = 1
Output: "a"
Explanation: The decoded string is "a" repeated 8301530446056247680 times.
The 1st letter is "a".

Solution

Method 1 - Decode the string

To decode the string and return the kth letter, we can follow these key steps:

  1. Calculate the Total Length of the Decoded String:
    • Iterate through the encoded string to calculate the length of the decoded string. During this:
      • If a character is a digit, multiply the current length by this digit.
      • If a character is a letter, increment the length by one.
  2. Determine the kth letter:
    • Traverse the string in reverse (from the end to the beginning).
    • Update k to be k % len to account for possible repetitions.
    • If a character is a digit, divide the current length by this digit.
    • If a character is a letter and k is 0 (after the modulo operation), this character is the kth letter.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public String decodeAtIndex(String s, int k) {
        long len = 0;

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                len *= (c - '0');
            } else {
                ++len;
            }
        }

        for (int i = s.length() - 1; i >= 0; i--) {
            k %= len;

            char c = s.charAt(i);

            if (k == 0 && Character.isLetter(c)) {
                return "" + c;
            }

            if (Character.isDigit(c)) {
                len /= (c - '0');
            } else {
                --len;
            }
        }
        return "";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        length: int = 0

        # Calculate the length of the decoded string
        for ch in s:
            if ch.isdigit():
                length *= int(ch)
            else:
                length += 1

        # Determine the kth letter
        for i in range(len(s) - 1, -1, -1):
            k %= length

            if k == 0 and s[i].isalpha():
                return s[i]

            if s[i].isdigit():
                length //= int(s[i])
            else:
                length -= 1

        return ""

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the input string s.
    • First, we iterate through the string to calculate the total length.
    • Then, we iterate through the string again to determine the kth letter.
  • 🧺 Space complexity: O(1), since we use only a few variables to store the current length, index, and the modulo result.