Decoded String at Index - Practice Coding Problems

Decoded String at Index - Problem

String Stack Medium

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 k-th letter (1-indexed) in the decoded string.

Input & Output

Example 1 — Basic Case

$ Input: s = "leet2code3", k = 10

› Output: "o"

💡 Note: The decoded string is "leetleetcodeleetleetcodeleetleetcode". The 10th letter is "o".

Example 2 — Simple Multiplication

$ Input: s = "ha22", k = 5

› Output: "h"

💡 Note: The decoded string is "hahahaha". The 5th letter is "h".

Example 3 — Single Character

$ Input: s = "a2345678999999999999999", k = 1

› Output: "a"

💡 Note: The decoded string starts with "a", so the 1st letter is "a".

Constraints

2 ≤ s.length ≤ 100
s consists of lowercase English letters and digits 2-9
s starts with a letter
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Encoded string with letters and digits

Decoding Process

Letters add characters, digits repeat the string

Smart Solution

Work backwards instead of building full string

Key Takeaway

🎯 Key Insight: Work backwards using modular arithmetic instead of building the exponentially large decoded string

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to work backwards instead of building the entire decoded string. Calculate the total size first, then work backwards from position k using modulo arithmetic to find the target character without building the massive string. Best approach is reverse calculation with Time: O(N), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Reverse Calculation	O(N)	O(1)	Calculate total size first, then work backwards to find the target character
Brute Force - Build Full String	O(N)	O(N)	Build the complete decoded string and return the k-th character

Reverse Calculation — Algorithm Steps

Calculate total decoded string length
Work backwards from position k
When hitting a digit, reduce k by modulo operation
When hitting a letter at position 0, that's our answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Size

Find total decoded string length

Work Backwards

Reduce problem size at each step

Find Character

When k becomes 0, return the letter

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

char* solution(char* s, int k) {
    int len = strlen(s);
    
    // First pass: calculate total size
    long long size = 0;
    for (int i = 0; i < len; i++) {
        if (isdigit(s[i])) {
            size *= (s[i] - '0');
        } else {
            size += 1;
        }
    }
    
    // Second pass: work backwards
    for (int i = len - 1; i >= 0; i--) {
        k = k % size;
        if (k == 0 && isalpha(s[i])) {
            char* result = (char*)malloc(2);
            result[0] = s[i];
            result[1] = '\0';
            return result;
        }
        if (isdigit(s[i])) {
            size /= (s[i] - '0');
        } else {
            size -= 1;
        }
    }
    
    char* result = (char*)malloc(2);
    result[0] = '\0';
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int k;
    scanf("%d", &k);
    char* result = solution(s, k);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(N)

Two passes through the input string of length N

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

125.0K Views

Medium Frequency

~25 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Reverse Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler