LeetCode 3304 - Find the K-th Character in String Game I

The problem defines an infinite string-building process that starts with the string "a". At every operation, we take the current string and create a transformed version where every character is replaced by the next character in the alphabet.

leetcodeeasymathbit-manipulationrecursionsimulation

LeetCode Problem 3304

Difficulty: 🟢 Easy
Topics: Math, Bit Manipulation, Recursion, Simulation

Solution

Problem Understanding

The problem defines an infinite string-building process that starts with the string "a".

At every operation, we take the current string and create a transformed version where every character is replaced by the next character in the alphabet. Then we append this transformed string to the original string.

For example:

  • "a" becomes "ab"
  • "ab" becomes "abbc"
  • "abbc" becomes "abbcbccd"

The transformation rule is simple:

  • 'a' becomes 'b'
  • 'b' becomes 'c'
  • ...
  • 'z' becomes 'a'

The input is a single integer k, representing the position of the character we want to find in the infinitely growing string. Positions are 1-indexed.

The goal is to return the character located at index k after enough operations have been performed so that the string length is at least k.

The constraints are very small:

  • 1 <= k <= 500

This immediately tells us that even relatively inefficient simulation approaches are acceptable. However, the problem becomes more interesting when we observe the structure of the generated string and derive a direct mathematical solution.

An important detail is that every operation doubles the string length. Starting from length 1, after:

  • 1 operation → length 2
  • 2 operations → length 4
  • 3 operations → length 8

and so on.

Important edge cases include:

  • k = 1, where the answer is simply 'a'
  • Positions exactly at powers of two, because they mark boundaries between original and appended segments
  • Characters near wrapping boundaries such as 'z' -> 'a', although with k <= 500 we never reach enough increments to overflow far beyond the alphabet size

Approaches

Brute Force Simulation

The most direct approach is to literally simulate the process described in the problem.

We start with:

word = "a"

At every iteration:

  1. Generate a transformed version where each character is replaced by its next alphabet character.
  2. Append the transformed string to the original string.
  3. Continue until the string length becomes at least k.

Once the generated string is long enough, we simply return word[k - 1].

This approach is straightforward and mirrors the problem statement exactly, which makes correctness easy to reason about.

However, the string doubles in size after every operation. Although the constraints are small enough for this solution to pass, the approach becomes inefficient for larger values because repeated string construction requires additional memory and copying.

Optimal Observation

The key observation is that the generated string follows a recursive structure.

At every step:

new_word = old_word + shifted(old_word)

The second half is always the first half shifted by one character.

This means:

  • If a position lies in the first half, its value is identical to the corresponding position in the previous iteration.
  • If a position lies in the second half, its value is the corresponding first-half character shifted by one.

This structure allows us to work backward from position k toward position 1.

Another important insight is that the number of shifts applied to the original 'a' equals the number of times we move into the second half during this backward traversal.

That count is exactly the number of set bits in k - 1.

Therefore:

answer = 'a' + popcount(k - 1)

This gives a very compact and efficient solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k) O(k) Explicitly builds the string until length reaches k
Optimal O(log k) O(1) Counts how many times the index falls into the appended half

Algorithm Walkthrough

  1. Convert the problem into zero-based indexing by computing k - 1.

The recursive structure becomes easier to analyze with zero-based positions. 2. Count the number of set bits in k - 1.

Every set bit corresponds to one operation where the target character came from the appended half instead of the original half. 3. Start from character 'a'.

Each time the position comes from the appended half, the character increases by one in the alphabet. 4. Add the number of set bits to 'a'.

If the bit count is:

  • 0 → 'a'
  • 1 → 'b'
  • 2 → 'c'
  • and so on.
  1. Convert the resulting character code back into a character and return it.

Why it works

Each operation copies the previous string and appends a version shifted by one character. Working backward from index k, every time the index belongs to the second half, we know the character gained one increment. The total number of such increments equals the number of 1 bits in the binary representation of k - 1. Therefore the final character is determined entirely by the popcount of k - 1.

Python Solution

class Solution:
    def kthCharacter(self, k: int) -> str:
        shifts = bin(k - 1).count("1")
        return chr(ord('a') + shifts)

The implementation is extremely compact because the mathematical observation eliminates the need for simulation.

The expression:

k - 1

converts the position into zero-based indexing.

The call:

bin(k - 1).count("1")

counts the number of set bits, which represents how many times the character was shifted during the recursive generation process.

Finally:

chr(ord('a') + shifts)

moves forward in the alphabet by the required number of increments and converts the result back into a character.

Go Solution

func kthCharacter(k int) byte {
    shifts := 0
    n := k - 1

    for n > 0 {
        shifts += n & 1
        n >>= 1
    }

    return byte('a' + shifts)
}

The Go implementation performs the bit counting manually using bitwise operations.

The expression:

n & 1

checks whether the least significant bit is set.

The right shift:

n >>= 1

moves to the next bit.

Unlike Python, Go does not provide a built-in binary string conversion that is as convenient for this task, so manual popcount computation is cleaner and more efficient.

The function returns a byte, which matches the required signature and naturally represents a character in Go.

Worked Examples

Example 1

Input:

k = 5

First compute:

k - 1 = 4

Binary representation:

4 = 100

Count set bits:

popcount(100) = 1

Therefore:

'a' + 1 = 'b'

Result:

"b"

We can verify this with explicit generation:

Operation String
Initial a
1 ab
2 abbc
3 abbcbccd

The 5th character is:

b

Example 2

Input:

k = 10

Compute:

k - 1 = 9

Binary representation:

9 = 1001

Count set bits:

popcount(1001) = 2

Therefore:

'a' + 2 = 'c'

Result:

"c"

Complexity Analysis

Measure Complexity Explanation
Time O(log k) We examine each bit of k - 1
Space O(1) Only a few integer variables are used

The optimal solution only processes the binary representation of k - 1. Since a number with value k contains O(log k) bits, the runtime is logarithmic. No additional data structures proportional to the input size are allocated.

Test Cases

solution = Solution()

assert solution.kthCharacter(1) == "a"  # smallest possible input
assert solution.kthCharacter(2) == "b"  # first appended character
assert solution.kthCharacter(3) == "b"  # repeated structure
assert solution.kthCharacter(4) == "c"  # second-half shift
assert solution.kthCharacter(5) == "b"  # example case
assert solution.kthCharacter(10) == "c"  # example case
assert solution.kthCharacter(8) == "d"  # power of two boundary
assert solution.kthCharacter(16) == "e"  # larger power of two
assert solution.kthCharacter(31) == "e"  # many set bits
assert solution.kthCharacter(500) == chr(ord('a') + bin(499).count("1"))  # upper bound
Test Why
k = 1 Validates smallest boundary
k = 2 Tests first generated append
k = 3 Confirms recursive structure
k = 4 Tests multiple shifts
k = 5 Validates provided example
k = 10 Validates provided example
k = 8 Tests power-of-two boundary
k = 16 Tests deeper recursion levels
k = 31 Tests many set bits
k = 500 Validates upper constraint

Edge Cases

One important edge case is k = 1. Since the initial string already contains one character, no operations are required. A buggy implementation might accidentally apply transformations before checking the position. The current solution handles this correctly because k - 1 = 0, whose popcount is 0, producing 'a'.

Another important case occurs when k is a power of two. These positions correspond to the very end of a generation level and accumulate the maximum number of shifts for that level. For example, k = 8 gives k - 1 = 7, whose binary representation is 111, resulting in three shifts and the character 'd'. The bit-counting approach naturally captures this behavior.

A third edge case involves large values near the upper constraint, such as k = 500. A naive recursive or repeatedly copied string implementation could become inefficient for larger limits. The optimal solution avoids string construction entirely and only performs bit operations, so it scales efficiently even if the constraint were significantly larger.