#3304

Easy

LeetCode Problem Workspace

Find the K-th Character in String Game I

Find the K-th character in a progressively built string using math and bit manipulation efficiently.

math bit manipulation recursion simulation

Problem Statement

Alice starts with a string word = "a" and repeatedly performs an operation that doubles the string and appends the next letter in alphabetical order. The sequence continues indefinitely as Bob challenges Alice with a positive integer k.

Your task is to determine the K-th character in the infinitely growing string without constructing it entirely. Constraints ensure k is small enough to use a math and bit manipulation approach efficiently.

Examples

Example 1

Input: k = 5

Output: "b"

Initially, word = "a" . We need to do the operation three times:

Example 2

Input: k = 10

Output: "c"

Example details omitted.

Constraints

1 <= k <= 500

Solution Approach

Analyze String Growth Pattern

Recognize that each operation doubles the string and appends a new letter. Track the length at each step to determine where the K-th character falls. This identifies the recursion level needed for direct computation.

Use Bit Manipulation to Navigate

Observe that the doubling forms a binary-like tree. Use bit manipulation to trace back from position k to its origin character in the sequence. This avoids constructing the full string while maintaining constant space.

Compute K-th Character Directly

Combine the length tracking and bit-based navigation to compute the character at position k. Convert the recursion index to the corresponding letter using ASCII math. This yields O(log k) time and O(1) space.

Complexity Analysis

Metric	Value
Time	O(\log k)
Space	O(1)

Time complexity is O(log k) because each step halves the search space for the K-th character. Space complexity is O(1) since we avoid storing the full string and only track indices and lengths.

What Interviewers Usually Probe

Candidate immediately identifies the string doubling and letter increment pattern.
Candidate proposes a solution without constructing the entire string.
Candidate correctly applies bit manipulation or recursion to locate position k.

Common Pitfalls or Variants

Common pitfalls

Attempting to build the entire string, which exceeds reasonable space limits.
Misaligning the index during recursion or bit tracing.
Confusing the letter sequence or off-by-one errors when converting indices to characters.

Follow-up variants

Determine the K-th character when the starting string is a different single letter.
Generalize the problem to a custom alphabet or longer repeating patterns.
Find the last character after n doubling operations instead of a specific K-th position.

FAQ

How do I find the K-th character in String Game I without building the full string?

Use length tracking and bit manipulation to trace back to the original character recursively instead of simulating the entire string.

Why does this problem involve bit manipulation?

Each string doubling creates a binary-like structure, so bit operations can efficiently navigate positions to locate the K-th character.

What is the time complexity of finding the K-th character?

The time complexity is O(log k) because each step reduces the search space by half using the doubling pattern.

Can the solution handle the maximum constraint k = 500?

Yes, using the math and bit manipulation approach, no full string construction is needed, keeping operations efficient.

What are common mistakes when solving Find the K-th Character in String Game I?

Building the string fully, off-by-one errors in indices, and miscalculating the letter sequence are frequent mistakes.

terminal

Solution

Solution 1: Simulation

We can use an array $\textit{word}$ to store the string after each operation. When the length of $\textit{word}$ is less than $k$, we continuously perform operations on $\textit{word}$.

1

2

3

4

5

6

class Solution:
    def kthCharacter(self, k: int) -> str:
        word = [0]
        while len(word) < k:
            word.extend([(x + 1) % 26 for x in word])
        return chr(ord("a") + word[k - 1])

Continue Practicing

#3307 find the k th character in string game ii #3283 maximum number of moves to kill all pawns #3264 final array state after k multiplication operations i