Leetcode 880. Decoded String at Index

Problem Explanation

The problem wants us to decode a string following specific rules. The encoded string consists of English letters and digits from 2 to 9. When we encounter a letter, we append it to the decoded string. When we encounter a digit, we repeat the entire string accumulated so far d-1 more times where d is the digit. Now, given such an encoded string and an index K, we are asked to find and return the K-th letter of the decoded string (counting from 1).

Let's take an example to understand this.

Example: Consider the encoded string as "ab2c3". To decode this string, we start reading the characters one by one.

• First, we encountered 'a' which is a letter, so the decoded string becomes "a".
• Then, we encountered 'b', again a letter, so the decoded string becomes "ab".
• Next, we encountered '2' which is a digit. According to the rule, the entire decoded string becomes "abab".
• Then, we encountered 'c', so the decoded becomes "ababc".
• Finally, we encounter '3'. So, the final decoded string becomes "ababcababcababc".

Approach and Algorithm

We need to keep track of the size of the decoded string (let's call it size). This size will give us the total length of the decoded string till the present character while traversing the encoded string.

We first try building the decoded string in the forward direction till its size became equal to or larger than K.

However, doing so may result in extremely large strings as the input size increases, which might be inefficient due to space constraints.

So instead of actually constructing the string, we keep track of its length via size. If we come across a digit D, we multiply size with D; and for a letter increment size.

After we have the total length of the decoded string, we go backwards through our tape. Whenever K is a multiple of size, if the character at the K-th position in the string is a letter, that would be our answer. If not, we reduce the size accordingly and continue.

Python Solution

1
2python
3class Solution(object):
4    def decodeAtIndex(self, s, k):
5        size = 0
6        # Calculate size = length of decoded string
7        for c in s:
8            if c.isdigit():
9                size *= int(c)
10            else:
11                size += 1
12
13        for c in reversed(s):
14            k %= size
15            if k == 0 and c.isalpha():
16                return c
17
18            if c.isdigit():
19                size /= int(c)
20            else:
21                size -= 1

Java Solution

1
2java
3class Solution {
4    public String decodeAtIndex(String S, int K) {
5        long size = 0;
6        int N = S.length();
7
8        // Find size = length of decoded string
9        for (int i = 0; i < N; ++i) {
10            char c = S.charAt(i);
11            if (Character.isDigit(c))
12                size *= c - '0';
13            else
14                size++;
15        }
16        for (int i = N-1; i >= 0; --i) {
17            char c = S.charAt(i);
18            if (Character.isDigit(c)) {
19                size /= c - '0';
20                K %= size;
21            } else if (K % size-- == 0)
22                return String.valueOf(c);
23        }
24
25        throw null;
26    }
27}

JavaScript Solution

1
2javascript
3var decodeAtIndex = function(s, K) {
4    let size = 0;
5    for (const ch of s) {
6        if (ch >= '0' && ch <= '9') {
7            size *= parseInt(ch);
8        } else {
9            size++;
10        }
11    }
12    for (let i = s.length - 1; i >= 0; i--) {
13        let ch = s.charAt(i);
14        if (ch >= '0' && ch <= '9') {
15            size = Math.floor(size / parseInt(ch));
16            K %= size;
17        } else if (K % size === 0) {
18            return ch;
19        } else {
20            size--;
21        }
22    }
23};
24

C++ Solution

1
2cpp
3class Solution {
4public:
5    string decodeAtIndex(string s, int k) {
6        long size = 0;  
7        for (auto ch : s)
8            if (isdigit(ch)) size *= ch - '0';
9            else ++size;
10        for (int i = s.length() - 1; i >= 0; --i) {
11            k %= size;
12            if (k == 0 && isalpha(s[i])) return string(1, s[i]);
13            if (isdigit(s[i])) size /= s[i] - '0';
14            else --size;
15        }
16        return "";
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public string DecodeAtIndex(string S, int K) {
5        long size = 0;
6        int N = S.Length;
7
8        // Find size = length of decoded string
9        for (int i = 0; i < N; ++i) {
10            char c = S[i];
11            if (Char.IsDigit(c))
12                size *= c - '0';
13            else
14                size++;
15        }
16
17        for (int i = N-1; i >= 0; --i) {
18            char c = S[i];
19            if (Char.IsDigit(c)) {
20                size /= c - '0';
21                K %= (int)size;
22            } else if (K % size-- == 0)
23                return c.ToString();
24        }
25
26        throw null;
27    }
28}

Go Solution

1
2go
3func decodeAtIndex(S string, K int) string {
4    var n int64
5    var repeat []int
6    var idx []int64
7    for _, c := range S {
8        if '0' <= c && c <= '9' {
9            n *= int64(c - '0')
10        } else {
11            n++
12        }
13        repeat = append(repeat, int(c-'0'))
14        idx = append(idx, n)
15    }
16    for i := len(S) - 1; i >= 0; i-- {
17        if 'a' <= S[i] && S[i] <= 'z' {
18            if K == int(idx[i]) || K == 0 {
19                return string(S[i])
20            }
21        } else {
22            if K == int(idx[i]) {
23                K--
24            }
25            K %= int(idx[i]) / repeat[i]
26        }
27    }
28    return ""
29}

Kotlin Solution

1
2kotlin
3fun decodeAtIndex(s: String, K: Int): String? {
4    var length: Long = 0
5    var i = 0
6    while (i < s.length) {
7        if (Character.isDigit(s[i])) {
8            length *= (s[i] - '0').toLong()
9        } else {
10            length++
11        }
12        if (K <= length) break
13        i++
14    }
15    while (i >= 0) {
16        if (Character.isDigit(s[i])) {
17            length /= (s[i] - '0').toLong()
18            K %= length.toInt()
19        } else if (length.toLong() == K.toLong() || K == 0) {
20            return s[i].toString()
21        } else {
22            length--
23        }
24        i--
25    }
26    return null
27}

It's important to note that the problem is a decoding issue at its core, and we solved it by capturing the number of times for repeating patterns with numbers and tracking the alphabet content until that point. We then used a backward run against the run-length to find the exact position of our solution character.

We have to handle every character of the to-be-decoded string, so it's important to note that the time complexity of these solutions is O(n), ignoring the possible multiplication operation on the big integer with a specific digit. The space complexity also turns out to be O(n) as we don't store a complete decoded string but only the string length.