Move from brute-force thinking to an efficient approach using stack strategy.
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:
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 <= 100s consists of lowercase English letters and digits 2 through 9.s starts with a letter.1 <= k <= 109k is less than or equal to the length of the decoded string.263 letters.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Stack
"leet2code3" 10
"ha22" 5
"a2345678999999999999999" 1
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #880: Decoded String at Index
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;
}
}
}
}
// Accepted solution for LeetCode #880: Decoded String at Index
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--
}
}
}
# Accepted solution for LeetCode #880: Decoded String at Index
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
// Accepted solution for LeetCode #880: Decoded String at Index
struct Solution;
impl Solution {
fn decode_at_index(s: String, k: i32) -> String {
let mut k = k as u64;
let s: Vec<char> = s.chars().collect();
let n = s.len();
let mut size = 0;
for i in 0..n {
match s[i] {
'0'..='9' => {
size *= (s[i] as u8 - b'0') as u64;
}
_ => {
size += 1;
}
}
}
let mut res = "".to_string();
for i in (0..n).rev() {
k %= size;
match s[i] {
'0'..='9' => {
size /= (s[i] as u8 - b'0') as u64;
}
_ => {
if k == 0 {
res = s[i].to_string();
break;
} else {
size -= 1;
}
}
}
}
res
}
}
#[test]
fn test() {
let s = "leet2code3".to_string();
let k = 10;
let res = "o".to_string();
assert_eq!(Solution::decode_at_index(s, k), res);
}
// Accepted solution for LeetCode #880: Decoded String at Index
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;
}
}
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.