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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

1
2
3
4


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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'))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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.