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.

#3304

Easy

auto_awesome数学·位运算

LeetCode 题解工作台

找出第 K 个字符 I

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a" 。给定一个正整数 k 。现在 Bob 会要求 Alice 执行以下操作无限次 : 将 word 中的每个字符更改为英文字母表中的下一个字符来生成一个新字符串，并将其追加到原始的 word…

数学位运算递归模拟

题目描述

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个正整数 k。

现在 Bob 会要求 Alice 执行以下操作 无限次 :

将 word 中的每个字符更改为英文字母表中的 下一个 字符来生成一个新字符串，并将其追加到原始的 word。

例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行足够多的操作后， word 中至少存在 k 个字符，此时返回 word 中第 k 个字符的值。

示例 1:

输入：k = 5

输出："b"

解释：

最初，word = "a"。需要进行三次操作:

生成的字符串是 "b"，word 变为 "ab"。
生成的字符串是 "bc"，word 变为 "abbc"。
生成的字符串是 "bccd"，word 变为 "abbcbccd"。

示例 2:

输入：k = 10

输出："c"

提示：

1 <= k <= 500

lightbulb

解题思路

方法一：模拟

我们可以使用一个数组 $\textit{word}$ 来存储每次操作后的字符串，当 $\textit{word}$ 的长度小于 $k$ 时，我们不断地对 $\textit{word}$ 进行操作。

最后返回 $\textit{word}[k - 1]$ 即可。

时间复杂度 $O(k)$ ，空间复杂度 $O(k)$ 。其中 $k$ 为输入参数。

1

2

3

4

5

6

7

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])

speed

复杂度分析

指标	值
时间	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.
空间	O(1)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#3307 找出第 K 个字符 II #3283 吃掉所有兵需要的最多移动次数 #3264 K 次乘运算后的最终数组 I