Find the K-th Character in String Game I

EASY

Description

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 k^th 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

Approaches

Checkout 3 different approaches to solve Find the K-th Character in String Game I. Click on different approaches to view the approach and algorithm in detail.

Direct Simulation

This approach directly follows the problem description. We start with the initial string "a" and repeatedly apply the generation operation until the string is long enough to contain the k-th character.

Algorithm

Initialize a StringBuilder word with the value "a".
Use a while loop that continues as long as the length of word is less than k.
Inside the loop, create a new StringBuilder called nextPart to build the transformed string.
Iterate through each character of the current word. For each character c, calculate its successor (e.g., 'a' becomes 'b', 'z' becomes 'a') and append it to nextPart.
After iterating through the entire word, append the nextPart to the word.
Once the while loop terminates, word will have a length of at least k.
The final answer is the character at index k-1 of the word.

The algorithm follows these steps:

Initialize a StringBuilder word with the value "a".
Use a while loop that continues as long as the length of word is less than k.
Inside the loop, create a new StringBuilder called nextPart to build the transformed string.
Iterate through each character of the current word. For each character c, calculate its successor (e.g., 'a' becomes 'b', 'z' becomes 'a') and append it to nextPart.
After iterating through the entire word, append the nextPart to the word.
Once the while loop terminates, word will have a length of at least k.
The final answer is the character at index k-1 of the word.

class Solution {
    public char findKthCharacter(int k) {
        StringBuilder word = new StringBuilder("a");
        while (word.length() < k) {
            StringBuilder nextPart = new StringBuilder();
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (c == 'z') {
                    nextPart.append('a');
                } else {
                    nextPart.append((char)(c + 1));
                }
            }
            word.append(nextPart);
        }
        return word.charAt(k - 1);
    }
}

Complexity Analysis

Time Complexity: O(L) where `L` is the smallest power of 2 greater than or equal to `k`. Since `L < 2k`, this is effectively O(k). The total work involves creating strings of lengths 1, 2, 4, ..., up to `L/2`, which sums to O(L).Space Complexity: O(L) or O(k), where `L` is the smallest power of 2 greater than or equal to `k`. This is because we need to store the generated string, which has a length proportional to `k`.

Pros and Cons

Pros:

Simple to understand and implement as it directly models the process described in the problem.

Cons:

Inefficient in terms of both time and space, especially for larger values of k.
Builds a potentially large string in memory, which is unnecessary.

Code Solutions

Checking out 3 solutions in different languages for Find the K-th Character in String Game I. Click on different languages to view the code.

class Solution {
public
  char kthCharacter(int k) {
    List<Integer> word = new ArrayList<>();
    word.add(0);
    while (word.size() < k) {
      for (int i = 0, m = word.size(); i < m; ++i) {
        word.add((word.get(i) + 1) % 26);
      }
    }
    return (char)('a' + word.get(k - 1));
  }
}

Video Solution

Watch the video walkthrough for Find the K-th Character in String Game I

Patterns:

MathRecursionBit Manipulation