Find the K-th Character in String Game I - Practice Coding Problems

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

Alice and Bob are playing a string transformation game. Initially, Alice has a string word = "a". You are given a positive integer k.

Bob will ask Alice to perform the following operation repeatedly:

Generate a new string by changing each character in word to its next character in the English alphabet
Append this new string to the original word

For example:

Performing the operation on "c" generates "cd" (c → d, then append)
Performing the operation on "zb" generates "zbac" (z → a, b → c, then append)

Return the value of the k-th character in word, after enough operations have been performed for word to have at least k characters.

Input & Output

Example 1 — Basic Case

$ Input: k = 5

› Output: b

💡 Note: Step 0: "a" → Step 1: "ab" → Step 2: "abbc" → The 5th character (index 4) is 'b'

Example 2 — Small k

$ Input: k = 1

› Output: a

💡 Note: The 1st character is always 'a' since we start with "a"

Example 3 — Edge Case

$ Input: k = 4

› Output: c

💡 Note: Step 0: "a" → Step 1: "ab" → Step 2: "abbc" → The 4th character is 'c'

Constraints

1 ≤ k ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

k = 5 (find 5th character)

Process

String grows: a → ab → abbc → ...

Output

5th character is 'b'

Key Takeaway

🎯 Key Insight: The binary representation of (k-1) directly tells us how many character transformations to apply

Asked in

M Meta 15 G Google 12

The key insight is recognizing the exponential growth pattern where the string length doubles each operation. The most efficient approach uses bit manipulation to count '1' bits in the binary representation of (k-1), giving us the number of character transformations needed. Time: O(log k), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation	O(log k)	O(1)	Use binary representation to directly calculate the k-th character without recursion
Simulation - Build String	O(k)	O(k)	Directly simulate the game by building the string until it has k characters
Mathematical Pattern Recognition	O(log k)	O(log k)	Recognize that string length doubles each step, use math to find which generation contains k-th character

Bit Manipulation — Algorithm Steps

Convert k-1 to binary
For each '1' bit from right to left, increment the character
Handle wraparound from 'z' to 'a'

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert

k-1 = 4 = 100₂

Count Bits

Count '1' bits in binary representation

Transform

Apply transformations based on bit count

Code -

solution.c — C

#include <stdio.h>

char solution(int k) {
    int result = 0;
    k -= 1; // Convert to 0-indexed
    
    while (k > 0) {
        if (k & 1) { // If current bit is 1
            result += 1;
        }
        k >>= 1; // Right shift by 1 bit
    }
    
    return 'a' + (result % 26);
}

int main() {
    int k;
    scanf("%d", &k);
    char result = solution(k);
    printf("%c\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log k)

We process each bit in the binary representation of k-1, which has log k bits

⚡ Linearithmic

Space Complexity

O(1)

We only use a constant amount of extra space for variables

✓ Linear Space

23.0K Views

Medium Frequency

~15 min Avg. Time

850 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

Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler