# Find the K-th Character in String Game I
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-k-th-character-in-string-game-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-k-th-character-in-string-game-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## 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.

**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
## 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.
**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`.
**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.
### Explanation
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`.

```java
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);
    }
}
```
### 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`.

## Recursive Divide and Conquer
This approach leverages the recursive structure of the string generation. The string at any step `n` is formed by the string from step `n-1` followed by its transformed version. This allows us to find the k-th character without building the entire string.
**Time:** O(log k). The recursion depth is `log(L)`, where `L` is the smallest power of 2 >= `k`. Each step of the recursion takes constant time. · **Space:** O(log k) due to the recursion call stack. The depth of the recursion is logarithmic with respect to `k`.
**Pros:** Much more efficient than simulation as it avoids constructing the large string.; Logarithmic time complexity is a significant improvement.
**Cons:** Uses recursion, which adds some overhead and has a space complexity proportional to the recursion depth.
### Explanation
This approach is based on the observation that the string at step `n`, `S_n`, is composed of the string from the previous step, `S_{n-1}`, followed by its transformed version, `T(S_{n-1})`. This allows us to recursively narrow down the position of the `k`-th character without building the full string.

The algorithm is as follows:
*   First, determine the length of the final string required. This will be the smallest power of 2, let's call it `L`, that is greater than or equal to `k`.
*   Define a recursive function, say `solve(length, k)`, which finds the `k`-th character in a generated string of the given `length`.
*   **Base Case:** If `length` is 1, the string is "a", so the function returns 'a'.
*   **Recursive Step:**
    *   Calculate the midpoint `mid = length / 2`.
    *   If `k` is in the first half (i.e., `k <= mid`), the character is part of the original `S_{n-1}`. We make a recursive call `solve(mid, k)`.
    *   If `k` is in the second half (i.e., `k > mid`), the character is part of the transformed `T(S_{n-1})`. We find its corresponding character in the first half by recursing with `solve(mid, k - mid)`, and then apply the transformation (increment the character, wrapping 'z' to 'a').
*   The initial call to the function will be `solve(L, k)`.

```java
class Solution {
    public char findKthCharacter(int k) {
        long length = 1;
        while (length < k) {
            length *= 2;
        }
        return solve(length, k);
    }

    private char solve(long length, int k) {
        if (length == 1) {
            return 'a';
        }
        long mid = length / 2;
        if (k <= mid) {
            return solve(mid, k);
        } else {
            char prevChar = solve(mid, (int)(k - mid));
            if (prevChar == 'z') {
                return 'a';
            } else {
                return (char)(prevChar + 1);
            }
        }
    }
}
```
### Algorithm
*   First, determine the length of the final string required. This will be the smallest power of 2, let's call it `L`, that is greater than or equal to `k`.
*   Define a recursive function, say `solve(length, k)`, which finds the `k`-th character in a generated string of the given `length`.
*   **Base Case:** If `length` is 1, the string is "a", so the function returns 'a'.
*   **Recursive Step:**
    *   Calculate the midpoint `mid = length / 2`.
    *   If `k` is in the first half (i.e., `k <= mid`), the character is part of the original string from the previous step. We make a recursive call `solve(mid, k)`.
    *   If `k` is in the second half (i.e., `k > mid`), the character is part of the transformed string. We find its corresponding character in the first half by recursing with `solve(mid, k - mid)`, and then apply the transformation (increment the character, wrapping 'z' to 'a').
*   The initial call to the function will be `solve(L, k)`.

## Bit Manipulation (Optimal)
This is the most efficient approach, derived from the recursive pattern. It observes that the number of transformations applied to the base character 'a' corresponds to the number of set bits (1s) in the binary representation of `k-1`.
**Time:** O(log k) or O(1). `Integer.bitCount(k)` is often a single hardware instruction, making it O(1). If implemented as a loop, it takes O(log k) time as it iterates through the bits of `k`. · **Space:** O(1). It uses a constant amount of extra space, regardless of the value of `k`.
**Pros:** Extremely efficient in both time and space.; Provides a direct mathematical solution without simulation or recursion.; Very simple and concise to implement.
**Cons:** The logic is less intuitive and requires understanding the connection between the recursive structure and binary representations.
### Explanation
This optimal approach is derived from a deeper analysis of the recursive pattern. The key insight is that the final character depends on how many times we have to take the "transformed" half of the string during the recursive process. Each time we do, one transformation is applied.

The algorithm is as follows:
*   The problem can be mapped to a binary representation. Let's use 0-based indexing, so we consider the character at index `k-1`.
*   The decision to go to the first half or second half in the recursive approach corresponds to checking the bits of `k-1` from most significant to least significant.
*   A transformation is applied if and only if the corresponding bit is 1.
*   Therefore, the total number of transformations applied to the initial character 'a' is simply the total number of set bits (1s) in the binary representation of `k-1`. This is also known as the population count or Hamming weight.
*   The algorithm simplifies to:
    1.  Calculate `p = Integer.bitCount(k - 1)`.
    2.  The result is the character 'a' shifted `p` times. Due to the wrap-around from 'z' to 'a', this is `(char)('a' + p % 26)`.

```java
class Solution {
    public char findKthCharacter(int k) {
        // The number of transformations is the population count of (k-1).
        // For example, k=5 -> k-1=4 (100b). popcount=1. 'a' -> 'b'.
        // k=10 -> k-1=9 (1001b). popcount=2. 'a' -> 'b' -> 'c'.
        int transformations = Integer.bitCount(k - 1);
        
        // The final character is 'a' transformed 'transformations' times.
        // Since 'z' wraps to 'a', this is equivalent to adding modulo 26.
        char result = (char)('a' + transformations % 26);
        
        return result;
    }
}
```
### Algorithm
*   Convert the 1-based index `k` to a 0-based index by subtracting 1.
*   Calculate the number of set bits (1s) in the binary representation of `k-1`. This is known as the population count.
*   Let the population count be `p`. This `p` represents the total number of transformations applied to the base character 'a'.
*   The final character is obtained by shifting 'a' by `p` positions in the alphabet.
*   To handle the wrap-around from 'z' to 'a', the calculation is `(char)('a' + p % 26)`.

# Solutions
### Java

```java
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));
  }
}

```

### CPP

```cpp
class Solution {
public:
  char kthCharacter(int k) {
    vector<int> word;
    word.push_back(0);
    while (word.size() < k) {
      int m = word.size();
      for (int i = 0; i < m; ++i) {
        word.push_back((word[i] + 1) % 26);
      }
    }
    return 'a' + word[k - 1];
  }
};

```

### Python

```python
class Solution:
    def kthCharacter(self, k: int) -> str: word = [0] while len(word) < k: word . extend([(x + 1) % 26 for x in word]) return chr(ord("a") + word[k - 1])

```