# Find the K-th Character in String Game II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-k-th-character-in-string-game-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-k-th-character-in-string-game-ii
**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`. You are also given an integer array `operations`, where `operations[i]` represents the **type** of the `ith` operation.

Now Bob will ask Alice to perform **all** operations in sequence:

* If `operations[i] == 0`, **append** a copy of `word` to itself.
* If `operations[i] == 1`, 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 performing all the operations.

**Note** that the character `'z'` can be changed to `'a'` in the second type of operation.

**Example 1:**

**Input:** k = 5, operations = \[0,0,0\]

**Output:** "a"

**Explanation:**

Initially, `word == "a"`. Alice performs the three operations as follows:

* Appends `"a"` to `"a"`, `word` becomes `"aa"`.
* Appends `"aa"` to `"aa"`, `word` becomes `"aaaa"`.
* Appends `"aaaa"` to `"aaaa"`, `word` becomes `"aaaaaaaa"`.

**Example 2:**

**Input:** k = 10, operations = \[0,1,0,1\]

**Output:** "b"

**Explanation:**

Initially, `word == "a"`. Alice performs the four operations as follows:

* Appends `"a"` to `"a"`, `word` becomes `"aa"`.
* Appends `"bb"` to `"aa"`, `word` becomes `"aabb"`.
* Appends `"aabb"` to `"aabb"`, `word` becomes `"aabbaabb"`.
* Appends `"bbccbbcc"` to `"aabbaabb"`, `word` becomes `"aabbaabbbbccbbcc"`.

**Constraints:**

* `1 <= k <= 1014`
* `1 <= operations.length <= 100`
* `operations[i]` is either 0 or 1.
* The input is generated such that `word` has **at least** `k` characters after all operations.

# Approaches
## Brute Force Simulation
This approach directly simulates the string generation process described in the problem. It starts with the initial string "a" and applies each operation in the `operations` array one by one, updating the string at each step. After all operations are performed, it returns the character at the k-th position.
**Time:** O(L), where L is the length of the string. In the worst case, this is O(2^n), which is infeasible. · **Space:** O(L), where L is the length of the string. In the worst case, this is O(2^n), which is infeasible.
**Pros:** Simple to understand and follows the problem description directly.
**Cons:** Extremely inefficient in both time and space.; The length of the string grows exponentially, reaching up to `2^100` characters, which is far too large to store in any computer's memory.; This approach will result in `OutOfMemoryError` for most test cases that adhere to the problem's constraints.; It will also be too slow, leading to `TimeLimitExceeded` even if memory were not an issue.
### Explanation
The brute force method involves constructing the string step-by-step, exactly as the game's rules dictate. We begin with `word = "a"` and loop through the `operations` array. In each iteration, we double the string's length by either appending a copy of itself (for operation 0) or a transformed copy (for operation 1). We continue this until all operations are processed. Finally, we access the `k`-th character from the fully constructed string. Given the constraints (`k` up to `10^14`, `operations.length` up to 100), the final string can have up to `2^100` characters, making this approach practically impossible to execute.

```java
class Solution {
    // This is a conceptual implementation and will fail due to memory and time limits.
    public String findKthCharacter(long k, int[] operations) {
        StringBuilder word = new StringBuilder("a");

        for (int op : operations) {
            // Optimization: Stop if length is already greater than k.
            // Note: This is insufficient as k can be very large.
            if (word.length() >= k) {
                break;
            }

            if (op == 0) {
                word.append(word.toString());
            } else {
                StringBuilder transformed = new StringBuilder();
                for (int i = 0; i < word.length(); i++) {
                    char c = word.charAt(i);
                    if (c == 'z') {
                        transformed.append('a');
                    } else {
                        transformed.append((char)(c + 1));
                    }
                }
                word.append(transformed);
            }
        }

        // This cast is unsafe as k is a long and string length can exceed Integer.MAX_VALUE.
        return String.valueOf(word.charAt((int)(k - 1)));
    }
}
```
### Algorithm
*   Initialize a `StringBuilder` or a similar mutable string structure with the initial value `"a"`.
*   Iterate through each operation in the `operations` array from start to finish.
*   For each operation, modify the string according to the rules:
    *   If `operations[i] == 0`, append the current string to itself.
    *   If `operations[i] == 1`, generate a new string by transforming each character of the current string to the next in the alphabet (`'z'` becomes `'a'`). Then, append this new transformed string to the original.
*   To avoid running out of memory immediately, you can add an optimization to stop growing the string once its length exceeds `k`, as characters beyond the `k`-th position are not needed.
*   After all operations are completed (or the length is sufficient), retrieve the character at the `(k-1)`-th index (since `k` is 1-indexed).
*   Return this character as a string.

## Backward Iteration with Pre-calculated Lengths
Instead of building the string forwards, we can determine the k-th character by working backward from the final state. The key observation is that each operation doubles the string's length. This means the k-th character is either in the first half (the original string from the previous step) or the second half (the appended part). By repeatedly halving the problem space, we can trace back to the initial string "a" and find the character.
**Time:** O(n), where n is `operations.length`. The two loops for pre-calculation and backward iteration both run `n` times. · **Space:** O(n), where n is `operations.length`, for storing the `lengths` array.
**Pros:** Very efficient in time, with a linear complexity relative to the number of operations.; Avoids the memory and time blow-up of the brute-force approach by using a mathematical shortcut.; Handles large values of `k` correctly.
**Cons:** Requires extra space proportional to the number of operations to store the pre-calculated lengths.
### Explanation
This method avoids building the string by analyzing the structure of the operations. Since each operation doubles the length, we can determine if the `k`-th character is in the first or second half of the string at any stage. We work backward from the last operation.

First, we pre-calculate the length of the string before each operation and store it in an array. Then, we iterate from the last operation to the first. For each operation `i`, we check if our target index `k` (0-indexed) is greater than or equal to the length of the string before that operation, `len = 2^i`. If it is, the character is in the appended half. We then adjust `k` to be relative to this second half (`k = k - len`) and, if the operation was type 1, we note that one transformation must be applied. If `k < len`, the character is in the first half, and we simply move to the previous operation without changing `k` or the transformation count. This process continues until we've considered all operations. The final character is 'a' plus the total number of transformations counted.

```java
class Solution {
    public String findKthCharacter(long k, int[] operations) {
        int n = operations.length;
        long[] lengths = new long[n + 1];
        lengths[0] = 1;
        for (int i = 0; i < n; i++) {
            lengths[i + 1] = lengths[i] * 2;
            // Cap the length to avoid overflow and because exact length > k is not needed.
            if (lengths[i + 1] > k) {
                lengths[i + 1] = k + 1;
            }
        }

        k--; // Use 0-based indexing
        int transformCount = 0;
        for (int i = n - 1; i >= 0; i--) {
            long len = lengths[i];
            if (k >= len) {
                k -= len;
                if (operations[i] == 1) {
                    transformCount++;
                }
            }
        }

        char finalChar = (char) ('a' + (transformCount % 26));
        return String.valueOf(finalChar);
    }
}
```
### Algorithm
*   Adjust `k` to be 0-indexed by decrementing it: `k--`.
*   Create a `long` array, `lengths`, of size `n+1`, where `n` is the number of operations.
*   `lengths[i]` will store the length of the string *before* the `i`-th operation. Initialize `lengths[0] = 1`.
*   Populate the `lengths` array. For `i` from 0 to `n-1`, calculate `lengths[i+1] = lengths[i] * 2`. To prevent `long` overflow for large `n`, if the length exceeds `k`, we can cap it at a value larger than `k` (e.g., `k+1`), as the exact value beyond `k` doesn't affect the logic.
*   Initialize an integer `transformCount = 0`.
*   Iterate backward through the operations, from `i = n-1` down to `0`.
*   In each iteration, get the length of the string before the current operation: `len = lengths[i]`.
*   Check if the target index `k` falls in the second half of the string formed by operation `i`: `if (k >= len)`.
    *   If it does, update `k` to its position relative to the start of the second half: `k -= len`.
    *   If `operations[i]` was type 1, it means the second half was transformed, so increment `transformCount`.
*   After the loop, the base character is `'a'`. The final character is found by applying `transformCount` transformations to `'a'`, which is `(char)('a' + (transformCount % 26))`.

## Optimized Backward Iteration (O(1) Space)
This approach is an optimization of the backward iteration method. Instead of pre-calculating and storing all intermediate lengths in an array, we can calculate the required length on the fly inside the backward loop. This eliminates the need for `O(n)` extra space, making the solution highly efficient in both time and space.
**Time:** O(n), where n is `operations.length`. The single backward loop runs `n` times. · **Space:** O(1), as we do not use any auxiliary data structures that scale with the input size.
**Pros:** Most efficient solution with optimal time and space complexity.; Constant space usage makes it scalable regardless of the number of operations.
**Cons:** The logic for handling potential `long` overflow when calculating `2^i` might be slightly less intuitive at first glance.
### Explanation
This is the most optimized solution. It builds upon the backward iteration logic but improves space complexity to constant. The key insight is that the length of the string before operation `i` is always `2^i`. We don't need to store these lengths in an array; we can compute them as needed during our backward pass.

The algorithm remains the same: iterate from `i = n-1` down to `0`. In each step, calculate `len = 2^i`. A check is needed for `i >= 63`, as `1L << i` would overflow a `long`. Since `k` is at most `10^14` (which is less than `2^47`), if `i` is large, `len` will certainly be greater than `k`, meaning `k` is in the first half. For smaller `i`, we compute `len` and perform the same check as before: if `k >= len`, we adjust `k` and increment `transformCount` if the operation was type 1. This achieves the same result with `O(1)` space.

```java
class Solution {
    public String findKthCharacter(long k, int[] operations) {
        k--; // Use 0-based indexing
        int n = operations.length;
        int transformCount = 0;

        for (int i = n - 1; i >= 0; i--) {
            // The length of the string before operation i is 2^i.
            // If i >= 63, 1L << i would overflow. However, k (max 10^14) is much smaller
            // than 2^63, so k will always be in the first half. We can just continue.
            if (i >= 63) {
                continue;
            }
            
            long len = 1L << i;
            if (k >= len) {
                k -= len;
                if (operations[i] == 1) {
                    transformCount++;
                }
            }
        }

        char finalChar = (char) ('a' + (transformCount % 26));
        return String.valueOf(finalChar);
    }
}
```
### Algorithm
*   Adjust `k` to be 0-indexed: `k--`.
*   Initialize an integer `transformCount = 0`.
*   Iterate backward through the operations, from `i = n-1` down to `0`.
*   In each iteration, we need the length of the string before operation `i`, which is `2^i`. We can calculate this on the fly.
*   A `long` can store up to `2^63 - 1`. If `i >= 63`, then `2^i` will be larger than any `long`, including `k`. In this case, `k` must be in the first half, so we can simply continue to the next iteration.
*   If `i < 63`, calculate `len = 1L << i`.
*   Check if the target index `k` falls in the second half: `if (k >= len)`.
    *   If it does, update `k` to its position relative to the start of the second half: `k -= len`.
    *   If `operations[i]` was type 1, increment `transformCount`.
*   After the loop, the base character is `'a'`. The final character is found by applying `transformCount` transformations to `'a'`, which is `(char)('a' + (transformCount % 26))`.

# Solutions
### Java

```java
class Solution {
public
  char kthCharacter(long k, int[] operations) {
    long n = 1;
    int i = 0;
    while (n < k) {
      n *= 2;
      ++i;
    }
    int d = 0;
    while (n > 1) {
      if (k > n / 2) {
        k -= n / 2;
        d += operations[i - 1];
      }
      n /= 2;
      --i;
    }
    return (char)('a' + (d % 26));
  }
}

```

### CPP

```cpp
class Solution {
public:
  char kthCharacter(long long k, vector<int> &operations) {
    long long n = 1;
    int i = 0;
    while (n < k) {
      n *= 2;
      ++i;
    }
    int d = 0;
    while (n > 1) {
      if (k > n / 2) {
        k -= n / 2;
        d += operations[i - 1];
      }
      n /= 2;
      --i;
    }
    return 'a' + (d % 26);
  }
};

```

### Python

```python
class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str: n, i = 1, 0 while n < k: n *= 2 i += 1 d = 0 while n > 1: if k > n // 2: k -= n // 2 d += operations[i - 1] n //= 2 i -= 1 return chr(d % 26 + ord("a"))

```