Scale Engineer

Find the K-th Character in String Game I

Easy
#2934Time: 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: 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`.
Patterns
MathRecursionBit Manipulation

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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`.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem