Coding · Two pointers
Kth character of a repeat-encoded string
- Reported once
- Medium
- Software Engineer (campus)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
An encoded string is a list of blocks, each block being some letters followed by a whole number that says how many times those letters repeat, so ab3c2 decodes to abababcc. Given the encoded string and a 1-based position k, return the character at position k of the decoded string, or an empty string when k falls outside it, without building the decoded string. The reported statement writes a count after every block (even a count of 1), allows counts of several digits, and may split one run into parts such as a2a2b3b1; here a block with no number counts once. The decoded string can be far longer than the encoded one. A candidate report lists it in an online test, where the candidate simply decoded the string; avoiding that is the stronger answer.
Restated in our own words, not a quote from CRED or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
The format is the first thing to settle. I read an encoded string as blocks, where a block is a run of non-digit characters followed by a run of digits that gives the repeat count of the whole run before it: ab3c2 means ababab then cc. Can the count have several digits, like ab12c3? Does every block carry a count, even a count of 1? Can one run be split into parts, as a2a2b3b1 for four a's then four b's? Is k counted from 1, and what should I return when k is past the end? Can groups nest, like a2(bc)3?
The reported statement answers most of this: lowercase letters, a count after every block, counts of several digits, split runs allowed, and a 1-based position. I also accept a block with no number and count it once, return an empty string for an out-of-range k, and allow no nesting. This is not the LeetCode problem Decoded String at Index, where a digit repeats everything decoded so far. The candidate simply decoded the string and indexed it, so I would mention the version that never builds it as the improvement.
Brute force
Say the obvious answer and why it is too slow.
Decode everything, then index: expand each block into its repeated letters, concatenate, and return the character at position k. It is simple and fine for tiny inputs, and the decoded string is easy to print when debugging.
It fails on size. The decoded length is the sum over blocks of letters times count, so a ten-character input like a999999999 expands to a billion characters, and a few such blocks exhaust memory long before the answer is found. Even stopping the expansion as soon as k characters exist costs O(k) time and space, and k can be enormous. The reported follow-up asks exactly for this: answer without ever materialising the decoded string.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(L) time and space, where L is the decoded length and can be far larger than n
- Time
- O(n) for an encoded string of length n
- Space
- O(1) extra
The pattern is one pass over run-length blocks with index arithmetic. The decoded string is the blocks in order, and each block has a length you can compute without expanding it: the number of letters times the count. Position k lives in the first block where the total decoded length so far reaches k.
So walk the encoded string once, block by block, keeping consumed, the decoded length of all earlier blocks. For each block read its letters (remember where they start and end, no copying), then its count, and compute length = letters * count. If consumed + length is at least k, this block holds the answer: the offset inside the block is k - consumed - 1 (0-based), and because the block is its letters repeated, the character is the one at index offset mod letter-count. Otherwise add the length to consumed and move on.
Correctness rests on two facts: blocks appear in the decoded string in the same order as in the input, and inside a block the letters repeat with a period equal to their number. The comparison is "at least k", not "greater than", because a block whose last character sits exactly at position k contains it. The walk stops at the first block that reaches k, so consumed is always below k when we add to it.
Time is O(n) for an encoded string of n characters, and extra space is O(1): a few integers and indexes. Out loud: "I never decode. I add up block lengths until I pass k, then use k minus what came before, modulo the number of letters."
Walk it through
A dry run on the example, step by step.
| Block | Length | Before | After | Holds k? |
|---|---|---|---|---|
| ab x 3 | 6 | 0 | 6 | no |
| cd x 2 | 4 | 6 | 10 | no |
| e x 4 | 4 | 10 | 14 | no |
| fgh x 2 | 6 | 14 | 20 | yes |
Take ab3cd2e4fgh2 and k = 17. The blocks are ab repeated 3 times (6 characters), cd twice (4), e four times (4), and fgh twice (6), for 20 characters in all. The running total before each block is 0, 6, 10 and 14.
The first three blocks end at 6, 10 and 14, all below 17, so they are skipped. The fourth block ends at 20, which is at least 17, so it holds position 17. The offset inside it is 17 - 14 - 1 = 2, and 2 mod 3 = 2, so the answer is the letter at index 2 of fgh, which is h. Nothing longer than the input was ever built.
The code
Runnable JavaScript, checked against test cases.
function kthCharacter(encoded, k) {
if (k < 1) return "";
let consumed = 0;
let i = 0;
while (i < encoded.length) {
const textStart = i;
while (i < encoded.length && !(encoded[i] >= "0" && encoded[i] <= "9")) i++;
const textEnd = i;
let count = 0;
let hasCount = false;
while (i < encoded.length && encoded[i] >= "0" && encoded[i] <= "9") {
count = count * 10 + Number(encoded[i]);
hasCount = true;
i++;
}
if (!hasCount) count = 1;
const size = textEnd - textStart;
const length = size * count;
if (k <= consumed + length) return encoded[textStart + ((k - consumed - 1) % size)];
consumed += length;
}
return "";
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
A k below 1 or above the decoded length returns an empty string: the walk finishes without a hit and falls through. A block with no number repeats once, which happens at the end of the input or when the string is letters only. A count of 0 gives a block of length 0, so it never holds k and the walk skips it.
- Multi-digit counts: a12 reads both digits before multiplying, so it means twelve a's.
- Boundary positions: k equal to the last position of a block belongs to that block.
- Leading digits with no letters: a block of length 0, so it contributes nothing.
- Empty input: there are no blocks, so every k is out of range.
- Large counts: lengths must stay below about 9 quadrillion in JavaScript numbers; beyond that switch to BigInt.
Follow-ups to expect
Where the interviewer pushes next.
- How would you handle nesting such as a2(bc3)2 without decoding?
- If the same encoded string answers a million queries, how would you speed each one up?
- What changes if the counts or k do not fit in a 64-bit integer?
- How would you return the substring starting at position k with length m, again without decoding everything?
- How does this differ from the LeetCode problem where a digit repeats the whole decoded string so far, and how do you solve that one?
Where candidates slip
The mistakes this problem punishes.
Off-by-one errors lead the list: treating k as 0-based while the offset formula assumes 1-based, or using a strict comparison so that the last character of a block is attributed to the next one. Close behind is applying the count to only the last letter, reading ab3 as abbb instead of ababab.
Also: reading only one digit of a multi-digit count; treating a missing count as zero and silently deleting the final letters; indexing with k modulo the whole decoded length instead of the block's letter count; building the decoded string "just to check", which defeats the point; and splitting a run of letters into separate one-letter blocks.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.