Find the K-th Character in String Game I

Problem

Alice and Bob are playing a game. Initially, Alice has a string word = "a".

You are given a positive integer k.

Now Bob will ask Alice to perform the following operation forever :

• Generate a new string by changing each character in word to its next character in the English alphabet, and append it to the original word.

For example, performing the operation on "c" generates "cd" and performing the operation on "zb" generates "zbac".

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

Note that the character 'z' can be changed to 'a' in the operation.

Examples

Example 1

Input: k = 5

Output: "b"

Explanation:

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

  * Generated string is `"b"`, `word` becomes `"ab"`.
  * Generated string is `"bc"`, `word` becomes `"abbc"`.
  * Generated string is `"bccd"`, `word` becomes `"abbcbccd"`.

Example 2

Input: k = 10

Output: "c"

Constraints

• 1 <= k <= 500

Solution

Method 1 – Recursive Backtracking (Reverse Construction)

Intuition

The string doubles in size each operation, with the second half being the next character for each in the first half. To find the k-th character, we can "reverse" the process: if k is in the first half, it's the same as the previous step; if in the second half, it's the next character of the corresponding position in the first half. This allows us to work backwards recursively until we reach the base case.

Approach

1. If k == 1, return 'a'.
2. Find the largest power of 2 less than k (let's call it half).
3. If k <= half, recursively find the k-th character.
4. If k > half, recursively find the (k - half)-th character, then shift it to the next character in the alphabet (with 'z' cycling to 'a').

Code

C++

class Solution {
public:
    char findKthCharacter(int k) {
        if (k == 1) return 'a';
        int half = 1;
        while (half * 2 < k) half *= 2;
        char c = findKthCharacter(k <= half ? k : k - half);
        if (k <= half) return c;
        return c == 'z' ? 'a' : c + 1;
    }
};

Go

func findKthCharacter(k int) byte {
    if k == 1 {
        return 'a'
    }
    half := 1
    for half*2 < k {
        half *= 2
    }
    c := findKthCharacter(if k <= half { k } else { k - half })
    if k <= half {
        return c
    }
    if c == 'z' {
        return 'a'
    }
    return c + 1
}

Java

class Solution {
    public char findKthCharacter(int k) {
        if (k == 1) return 'a';
        int half = 1;
        while (half * 2 < k) half *= 2;
        char c = findKthCharacter(k <= half ? k : k - half);
        if (k <= half) return c;
        return c == 'z' ? 'a' : (char)(c + 1);
    }
}

Kotlin

class Solution {
    fun findKthCharacter(k: Int): Char {
        if (k == 1) return 'a'
        var half = 1
        while (half * 2 < k) half *= 2
        val c = findKthCharacter(if (k <= half) k else k - half)
        if (k <= half) return c
        return if (c == 'z') 'a' else c + 1
    }
}

Python

class Solution:
    def findKthCharacter(self, k: int) -> str:
        if k == 1:
            return 'a'
        half = 1
        while half * 2 < k:
            half *= 2
        c = self.findKthCharacter(k if k <= half else k - half)
        if k <= half:
            return c
        return chr((ord(c) - ord('a') + 1) % 26 + ord('a'))

Rust

impl Solution {
    pub fn find_kth_character(k: i32) -> char {
        if k == 1 {
            return 'a';
        }
        let mut half = 1;
        while half * 2 < k {
            half *= 2;
        }
        let c = Solution::find_kth_character(if k <= half { k } else { k - half });
        if k <= half {
            return c;
        }
        if c == 'z' {
            'a'
        } else {
            ((c as u8) + 1) as char
        }
    }
}

TypeScript

class Solution {
    findKthCharacter(k: number): string {
        if (k === 1) return 'a';
        let half = 1;
        while (half * 2 < k) half *= 2;
        const c = this.findKthCharacter(k <= half ? k : k - half);
        if (k <= half) return c;
        return c === 'z' ? 'a' : String.fromCharCode(c.charCodeAt(0) + 1);
    }
}

Complexity

• ⏰ Time complexity: O(log k), since we halve the problem size each time.
• 🧺 Space complexity: O(log k), due to recursion stack.