I am looking into LeetCode challenge 3304. Find the K-th Character in String Game I:

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.

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

I came up with this solution in C#:

public char KthCharacter(int k) {
    string word = "a";
    int min = 97, max = 122;
    int letter = 0;

    int i = 0;

    while (word.Length < k)
    {
        string tempStr = "";
   
        while (i < word.Length)
        {
            letter = word[i++];
            letter++;
            if (letter > max) letter = min;
            char temp = Convert.ToChar(letter);
            tempStr +=  new string(new char[] {temp});
        }
        
        word += tempStr;
        i=0;
    }

    return word[k-1];
}

Question

What is the Time Complexity (big O) of my solution?

I think it is O(Log N) for the outer loop, because the increment pattern of the word length is multiplied by 2 in the outer loop until the length is equal to or greater than k, whereas the inner loop that iterates through the given word, which increases twice in length per iteration, is O(N).

So is the time complexity O(N Log N)? And is the space complexity O(N) given the length of word expands based on the input?

What you write about the space complexity is correct. It is O(𝑘).

Concerning the time complexity:

The length of word doubles in each iteration of the outer loop, starting with length 1, so indeed the outer loop makes O(log𝑘) iterations.

The inner loop makes as many iterations as the length of word at that time. But the body of the inner loop has a statement that is not O(1), which is:

tempStr += temp;

This creates a new string, which means O(𝑚) characters are copied where 𝑚 is the new size of tempStr. So for one execution of the outer loop, we have this number of characters that are copied, given 𝑠 is the length of word:

1 + 2 + 3 + ... + 𝑠 = 𝑠(𝑠+1)/2 = O(𝑠²)

And knowing that 𝑠 takes values 2⁰, 2¹, 2², 2³, ..., 2^log𝑘, this sums up to:

O(2⁰ + 2² + 2⁴ + 2⁶ + ... + 2^2log𝑘)

= O(2^2log𝑘) = O(𝑘²)

Another algorithm

You have approached this code challenge with a rather brute force solution. This is not the most efficient way to approach it, not in terms of time nor of space.

This puzzle can be solved without actually building the string.

Here are some spoiler hints to achieve that:

Approach it from the reverse direction. If you would know the character at k, what does this tell you about the place where the character sits that was incremented in order to get this final character? Where is it positioned? If you can derive its position, can you repeat this approach to find the character that was incremented to get that one, ...etc?

Could the binary representation of k help with the previous hint? Or maybe when k would be the 0-based index instead of the 1-based position?

How do the 1-bits of k-1 in binary representation correspond to the number of increments applied to "a"?

And a spoiler implementation (using the hints):

public class Solution { public char KthCharacter(int k) { return Convert.ToChar(97 + int.PopCount(k-1) % 26); } }

Note that the modulo operator is not really needed when we see the constraints of the code challenge: as 𝑘 never exceeds 500, the maximum number of cumulative increments applied to "a" is 8, so the letters stay in the range of "a"..."i".