0624EasyMathBit ManipulationRecursionSimulation

Letter at a Position in the Growing Tag

Tracked in this browser only

Trains the technique from

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

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A label generator keeps one word, which starts out as the single letter "a".

In one round the generator takes the word it currently holds, makes a copy in which every letter is replaced by the next letter of the alphabet, so 'a' becomes 'b', 'b' becomes 'c' and so on, and then sticks that copy on the end of the word. The word therefore doubles in length each round: after the first round it reads "ab", after the second "abbc".

Rounds keep running until the word holds at least k letters. Return the k-th letter of the word, counting the first letter as position 1. The bound on k keeps every letter within the alphabet, so no letter ever has to step past 'z'.

Examples

Example 1

Input: k = 4
Output: "c"

After two rounds the word reads `"abbc"`, which already holds four letters, and its fourth letter is `"c"`.

Example 2

Input: k = 8
Output: "d"

After three rounds the word reads `"abbcbccd"`, and its eighth letter is `"d"`.

Example 3

Input: k = 12
Output: "d"

Four rounds give `"abbcbccdbccdcdde"`. Its twelfth letter is `"d"`.

Constraints

1 <= k <= 500

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def kth_character(k: int) -> str:

Java

public char kthCharacter(int k)

The intended approach

Time O(log k) — one pass over the bits of k - 1.Space O(1)

Work with the zero-based position `k - 1`. A round keeps the first half of the word exactly as it was and writes the second half one letter further on, so a position in the first half of a round inherits its letter unchanged while a position in the second half inherits it with one extra step. Halving the position repeatedly records those choices, and the choices are precisely the binary digits of `k - 1`. Counting the one bits therefore gives how far past `'a'` the letter sits, with no need to build the word.

Pythonentry point: kth_character

def kth_character(k):
    # O(log k) time, O(1) space. Number the positions from zero. A round leaves
    # the first half of the word untouched and writes the second half one letter
    # further along, so whether a position lands in the second half of a round
    # decides whether it picks up one extra step. Those decisions are exactly
    # the binary digits of the zero-based position, so the total number of steps
    # taken past 'a' is the count of one bits in k - 1.
    steps = bin(k - 1).count('1')
    return chr(ord('a') + steps)

The obvious version

Build the word for real. Starting from a single `'a'`, keep appending a letter-advanced copy of the whole word until it is long enough, then read off the requested position.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_kth_character(k):
    word = 'a'
    while len(word) < k:
        shifted = "".join(chr(ord(letter) + 1) for letter in word)
        word = word + shifted
    return word[k - 1]

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in