Problem Statement

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 leastk characters.

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

Constraints:

• 1 ≤ k ≤ 500

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"
Thus the kth element, i.e 5th element (index 4) = b

Example 2:

Input: k = 10
Output: "c"

Different Approaches

Brute Force Approach

The brute force idea is to build the string step by step until its length is at least k, then just return word[k - 1].

Code:

class Solution {
public:
    char kthCharacter(long long k) {
        string word = "a";
        while (word.size() < k) {
            string shifted;
            for (char ch : word) {
                shifted += (ch == 'z') ? 'a' : ch + 1;
            }
            word += shifted;
        }
        return word[k - 1];
    }
};

Complexity Analysis:

• Time Complexity:O(k)
  • In worst case (but grows exponentially per step)
• Space Complexity:O(k)
  • String grows until length ≥ k