Find the K-th Character in String Game II

Find the K-th Character in String Game II - Problem

Alice and Bob are playing a game. Initially, Alice has a string word = "a". You are given a positive integer k and an integer array operations, where operations[i] represents the type of the i-th operation.

Now Bob will ask Alice to perform all operations in sequence:

If operations[i] == 0, append a copy of word to itself.
If operations[i] == 1, generate a new string by changing each character in word to its next character in the English alphabet, and append it to the original word.

For example, performing operation 1 on "c" generates "cd" and performing operation 1 on "zb" generates "zbac".

Return the value of the k-th character in word after performing all the operations. Note that the character 'z' can be changed to 'a' in the second type of operation.

Input & Output

Example 1 — Basic Operations

$ Input: operations = [0,1,1,1], k = 5

› Output: c

💡 Note: Start with 'a'. Op[0]: 'a' → 'aa'. Op[1]: 'aa' → 'aabb'. Op[2]: 'aabb' → 'aabbbbcc'. Op[3]: 'aabbbbcc' → 'aabbbbccbbccccdd'. The 5th character is 'c'.

Example 2 — Only Copies

$ Input: operations = [0,0,0], k = 1

› Output: a

💡 Note: Start with 'a'. Each operation just copies the string: 'a' → 'aa' → 'aaaa' → 'aaaaaaaa'. The 1st character is always 'a'.

Example 3 — Single Shift

$ Input: operations = [1], k = 2

› Output: b

💡 Note: Start with 'a'. Op[1]: shift and append → 'ab'. The 2nd character is 'b'.

Constraints

1 ≤ operations.length ≤ 40
operations[i] is either 0 or 1
1 ≤ k ≤ 2^{operations.length}

Visualization

Tap to expand

Understanding the Visualization

Input

operations=[0,1,1,1], k=5

String Evolution

String grows: a→aa→aabb→aabbbbcc→aabbbbccbbccccdd

Output

5th character is 'c'

Key Takeaway

🎯 Key Insight: Instead of building exponentially large strings, trace backwards from the target position through the operations to determine the final character efficiently.

Asked in

G Google 15 M Meta 12 a Amazon 8

The key insight is that the string grows exponentially but we only need one character. Instead of building the full string, we can work backwards from the target position k through the operations to determine which character it represents. The optimal approach uses an iterative method to trace the path in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive with Memoization	O(2ⁿ)	O(n)	Use recursion to find the character without building the full string
Optimized Iterative Approach	O(n)	O(1)	Work backwards iteratively to find the character without recursion
Brute Force - Simulate All Operations	O(2ⁿ)	O(2ⁿ)	Build the entire string by performing each operation sequentially

Recursive with Memoization — Algorithm Steps

Work backwards from the final state
For each operation, determine if k is in original or appended half
If in appended half and operation was 1, apply alphabet shift
Recursively solve for the adjusted position

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Find character at position k

Divide

Check if k is in first or second half

Recurse

Apply shifts and recurse on adjusted position

Code -

solution.c — C

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

typedef struct {
    int opsIdx, pos, shifts;
    char result;
} MemoEntry;

MemoEntry memo[10000];
int memoSize = 0;

char findMemo(int opsIdx, int pos, int shifts) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].opsIdx == opsIdx && memo[i].pos == pos && memo[i].shifts == shifts) {
            return memo[i].result;
        }
    }
    return 0;
}

void addMemo(int opsIdx, int pos, int shifts, char result) {
    memo[memoSize].opsIdx = opsIdx;
    memo[memoSize].pos = pos;
    memo[memoSize].shifts = shifts;
    memo[memoSize].result = result;
    memoSize++;
}

char solve(int* operations, int operationsSize, int opsIdx, int pos, int shifts) {
    char cached = findMemo(opsIdx, pos, shifts);
    if (cached != 0) return cached;
    
    if (opsIdx == -1) {
        char result = ((shifts % 26) + 'a');
        addMemo(opsIdx, pos, shifts, result);
        return result;
    }
    
    int length = 1 << (operationsSize - opsIdx - 1);
    
    char result;
    if (pos <= length) {
        result = solve(operations, operationsSize, opsIdx - 1, pos, shifts);
    } else {
        int newShifts = shifts + (operations[opsIdx] == 1 ? 1 : 0);
        result = solve(operations, operationsSize, opsIdx - 1, pos - length, newShifts);
    }
    
    addMemo(opsIdx, pos, shifts, result);
    return result;
}

char solution(int* operations, int operationsSize, int k) {
    memoSize = 0;
    return solve(operations, operationsSize, operationsSize - 1, k, 0);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    int operations[100];
    int count = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        operations[count++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    int k;
    scanf("%d", &k);
    printf("%c\n", solution(operations, count, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Still explores exponential number of states in worst case

✓ Linear Growth

Space Complexity

O(n)

Recursion depth is n operations, plus memoization cache

⚡ Linearithmic Space

8.8K Views

Medium Frequency

~25 min Avg. Time

234 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

Recursive with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler