Decoded String at Index

• Initialize an empty StringBuilder to act as the tape.
• Iterate through each character of the input string s.
• If the character is a letter, append it to the StringBuilder.
• If the character is a digit d, take the current string in the StringBuilder and append it d-1 more times.
• After iterating through the entire string s, the StringBuilder will contain the fully decoded string.
• Return the character at index k-1 from the StringBuilder.

The idea is to use a mutable string, like Java's StringBuilder, to construct the decoded string. We process the encoded string s character by character. When we encounter a letter, we append it. When we see a digit d, we duplicate the current content of our StringBuilder d-1 times. This process continues until we have processed all of s. Finally, we access the character at the k-1 index (since k is 1-indexed) of the resulting string.

1class Solution {2    public String decodeAtIndex(String s, int k) {3        StringBuilder decodedString = new StringBuilder();4        for (char c : s.toCharArray()) {5            if (Character.isLetter(c)) {6                decodedString.append(c);7            } else {8                long d = c - '0';9                String currentTape = decodedString.toString();10                for (int i = 0; i < d - 1; i++) {11                    decodedString.append(currentTape);12                    // A small optimization could be to check if length > k here,13                    // but it doesn't save it from memory/time issues on large inputs.14                }15            }16        }17        return String.valueOf(decodedString.charAt(k - 1));18    }19}

This code will fail on examples like s = "a2345678999999999999999" because the length of the decoded string becomes astronomically large.

• Pass 1: Calculate Decoded String Size
  • Initialize a long variable size to 0.
  • Iterate through the encoded string s from left to right.
  • If the character c is a letter, increment size by 1.
  • If the character c is a digit d, multiply size by d.
• Pass 2: Work Backwards to Find the Character
  • Iterate through the encoded string s from right to left (from index n-1 to 0).
  • Let the current character be c.
  • For each character, first update k by taking it modulo the current size: k %= size.
  • If c is a letter:
    • If the updated k is 0 (or if k was originally a multiple of size), this letter is our answer. Return it.
    • Otherwise, this letter is not the one we're looking for. We effectively 'remove' it from the end by decrementing size: size--.
  • If c is a digit d:
    • We 'undo' the multiplication by dividing size by d: size /= d.

This approach cleverly avoids generating the massive decoded string. It works in two passes.

First Pass: We calculate the total length of the decoded string. We iterate through s, updating a size variable. If we see a letter, we increment size. If we see a digit d, we multiply size by d. We use a long for size to prevent overflow.

Second Pass: We iterate backwards from the end of s. At each step, we know the size of the string decoded up to that point. We want to find the k-th character. The key insight is that the k-th character in a string of length L repeated d times is the same as the (k-1) % L + 1-th character in the original string of length L. We can simplify this using k %= size. By repeatedly applying this logic and 'undoing' the operations (division for a digit, decrement for a letter), we can trace k back to the character it corresponds to in the original non-repeated parts of the string.

1class Solution {2    public String decodeAtIndex(String s, int k) {3        long size = 0;4        int n = s.length();5 6        // Pass 1: Calculate the total size of the decoded string.7        for (char c : s.toCharArray()) {8            if (Character.isDigit(c)) {9                size *= (c - '0');10            } else {11                size++;12            }13        }14 15        // Pass 2: Work backwards to find the k-th character.16        for (int i = n - 1; i >= 0; i--) {17            char c = s.charAt(i);18            // Cast k to long for the modulo operation to be safe.19            long k_long = k;20            k_long %= size;21 22            if (k_long == 0 && Character.isLetter(c)) {23                // This is the character we are looking for.24                // k_long == 0 means we are at the last character of the current segment.25                return String.valueOf(c);26            }27 28            if (Character.isDigit(c)) {29                // If it's a digit, we undo the multiplication.30                size /= (c - '0');31            } else {32                // If it's a letter, we undo the addition.33                size--;34            }35            // Update k for the next iteration.36            k = (int) k_long;37        }38 39        return ""; // Should not be reached given the problem constraints.40    }41}