Skip to main content

880. Decoded String at Index

medium

Find the k-th character of a string whose decoded form may be astronomically long. Solved by working backwards with modular arithmetic instead of materialising the full string.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an encoded string s. To decode the string: 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 k-th letter (1-indexed) in the decoded string.

Constraints

  • 2 <= s.length <= 100
  • s consists of lowercase English letters and digits 2 through 9.
  • s starts with a letter.
  • 1 <= k <= 10^9.
  • It is guaranteed that the decoded string has at least k letters.

Examples

Example 1

Input
s = "leet2code3", k = 10
Output
"o"

Explanation: Decoded string is "leetleetcodeleetleetcodeleetleetcode". The 10th letter is 'o'.

Example 2

Input
s = "ha22", k = 5
Output
"h"

Explanation: Decoded string is "hahahaha". The 5th letter is 'h'.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The decoded length can exceed 10^15 — never build it.

Hint 2

First pass: compute total decoded length by simulating multiplication on digits and increment on letters.

Hint 3

Second pass: walk the encoded string backwards. On a digit, divide size by d and reduce k modulo size. On a letter, if k % size == 0 return that letter; else decrement size.

Solution approach

Reveal approach

Two passes. Forward pass computes the total decoded length: on a digit d the running size multiplies by d, on a letter it increments. Backward pass walks s in reverse with that size in hand. On a digit d, divide size by d and replace k by k modulo size (with 0 mapping to size — the last block boundary). On a letter, if k == 0 return that letter; otherwise decrement size. The key insight is that the decoded string is built of repeated prefixes, so a single index in the giant string corresponds to a single index in some smaller prefix found by modulo. O(n) time and O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • math
  • modular-arithmetic
  • string-decoding

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Decoded String at Index and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →