Skip to content

880. Decoded String at Index

Description

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.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

  • 2 <= s.length <= 100
  • s consists of lowercase English letters and digits 2 through 9.
  • s starts with a letter.
  • 1 <= k <= 109
  • It is guaranteed that k is less than or equal to the length of the decoded string.
  • The decoded string is guaranteed to have less than 263 letters.

Solutions

Solution 1: Reverse Thinking

Thinking

The decoded tape is built from letters and repeat digits and can be far longer than \(10^{18}\); \(k\) is up to \(10^9\), so we must not materialize it. The \(k\)-th character is fixed by the last operation whose length covers \(k\).

Accumulate the decoded length \(m\) forward, then walk backward: a digit reduces \(k\) modulo the current length, and a letter with \(k\equiv 0\) is the answer. Two passes over \(s\) suffice.

We can first calculate the total length \(m\) of the decoded string, then traverse the string from back to front. Each time, we update \(k\) to be \(k \bmod m\), until \(k\) is \(0\) and the current character is a letter, then we return the current character. Otherwise, if the current character is a number, we divide \(m\) by this number. If the current character is a letter, we subtract \(1\) from \(m\).

The time complexity is \(O(n)\), where \(n\) is the length of the string. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        m = 0
        for c in s:
            if c.isdigit():
                m *= int(c)
            else:
                m += 1
        for c in s[::-1]:
            k %= m
            if k == 0 and c.isalpha():
                return c
            if c.isdigit():
                m //= int(c)
            else:
                m -= 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String decodeAtIndex(String s, int k) {
        long m = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (Character.isDigit(s.charAt(i))) {
                m *= (s.charAt(i) - '0');
            } else {
                ++m;
            }
        }
        for (int i = s.length() - 1;; --i) {
            k %= m;
            if (k == 0 && !Character.isDigit(s.charAt(i))) {
                return String.valueOf(s.charAt(i));
            }
            if (Character.isDigit(s.charAt(i))) {
                m /= (s.charAt(i) - '0');
            } else {
                --m;
            }
        }
    }
}

 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 {
public:
    string decodeAtIndex(string s, int k) {
        long long m = 0;
        for (char& c : s) {
            if (isdigit(c)) {
                m *= (c - '0');
            } else {
                ++m;
            }
        }
        for (int i = s.size() - 1;; --i) {
            k %= m;
            if (k == 0 && isalpha(s[i])) {
                return string(1, s[i]);
            }
            if (isdigit(s[i])) {
                m /= (s[i] - '0');
            } else {
                --m;
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func decodeAtIndex(s string, k int) string {
    m := 0
    for _, c := range s {
        if c >= '0' && c <= '9' {
            m *= int(c - '0')
        } else {
            m++
        }
    }
    for i := len(s) - 1; ; i-- {
        k %= m
        if k == 0 && s[i] >= 'a' && s[i] <= 'z' {
            return string(s[i])
        }
        if s[i] >= '0' && s[i] <= '9' {
            m /= int(s[i] - '0')
        } else {
            m--
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function decodeAtIndex(s: string, k: number): string {
    let m = 0n;
    for (const c of s) {
        if (c >= '1' && c <= '9') {
            m *= BigInt(c);
        } else {
            ++m;
        }
    }
    for (let i = s.length - 1; ; --i) {
        if (k >= m) {
            k %= Number(m);
        }
        if (k === 0 && s[i] >= 'a' && s[i] <= 'z') {
            return s[i];
        }
        if (s[i] >= '1' && s[i] <= '9') {
            m = (m / BigInt(s[i])) | 0n;
        } else {
            --m;
        }
    }
}

Comments