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 Sam K., 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

More Strings practice problems

See all Strings problems →