Find the K-th Character in String Game II

Hard

#2937Time: 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.

Patterns

Math Recursion Bit Manipulation

Prompt

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 i^th 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 k^th 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 <= 10¹⁴
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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    // This is a conceptual implementation and will fail due to memory and time limits.3    public String findKthCharacter(long k, int[] operations) {4        StringBuilder word = new StringBuilder("a");5 6        for (int op : operations) {7            // Optimization: Stop if length is already greater than k.8            // Note: This is insufficient as k can be very large.9            if (word.length() >= k) {10                break;11            }12 13            if (op == 0) {14                word.append(word.toString());15            } else {16                StringBuilder transformed = new StringBuilder();17                for (int i = 0; i < word.length(); i++) {18                    char c = word.charAt(i);19                    if (c == 'z') {20                        transformed.append('a');21                    } else {22                        transformed.append((char)(c + 1));23                    }24                }25                word.append(transformed);26            }27        }28 29        // This cast is unsafe as k is a long and string length can exceed Integer.MAX_VALUE.30        return String.valueOf(word.charAt((int)(k - 1)));31    }32}

Complexity

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.

Trade-offs

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.

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.

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

Walkthrough

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.

1class Solution {2    public String findKthCharacter(long k, int[] operations) {3        int n = operations.length;4        long[] lengths = new long[n + 1];5        lengths[0] = 1;6        for (int i = 0; i < n; i++) {7            lengths[i + 1] = lengths[i] * 2;8            // Cap the length to avoid overflow and because exact length > k is not needed.9            if (lengths[i + 1] > k) {10                lengths[i + 1] = k + 1;11            }12        }13 14        k--; // Use 0-based indexing15        int transformCount = 0;16        for (int i = n - 1; i >= 0; i--) {17            long len = lengths[i];18            if (k >= len) {19                k -= len;20                if (operations[i] == 1) {21                    transformCount++;22                }23            }24        }25 26        char finalChar = (char) ('a' + (transformCount % 26));27        return String.valueOf(finalChar);28    }29}

Complexity

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.

Trade-offs

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.

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.

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

Walkthrough

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.

1class Solution {2    public String findKthCharacter(long k, int[] operations) {3        k--; // Use 0-based indexing4        int n = operations.length;5        int transformCount = 0;6 7        for (int i = n - 1; i >= 0; i--) {8            // The length of the string before operation i is 2^i.9            // If i >= 63, 1L << i would overflow. However, k (max 10^14) is much smaller10            // than 2^63, so k will always be in the first half. We can just continue.11            if (i >= 63) {12                continue;13            }14            15            long len = 1L << i;16            if (k >= len) {17                k -= len;18                if (operations[i] == 1) {19                    transformCount++;20                }21            }22        }23 24        char finalChar = (char) ('a' + (transformCount % 26));25        return String.valueOf(finalChar);26    }27}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  char kthCharacter(long k, int[] operations) {4    long n = 1;5    int i = 0;6    while (n < k) {7      n *= 2;8      ++i;9    }10    int d = 0;11    while (n > 1) {12      if (k > n / 2) {13        k -= n / 2;14        d += operations[i - 1];15      }16      n /= 2;17      --i;18    }19    return (char)('a' + (d % 26));20  }21}

1class Solution {2public:3  char kthCharacter(long long k, vector<int> &operations) {4    long long n = 1;5    int i = 0;6    while (n < k) {7      n *= 2;8      ++i;9    }10    int d = 0;11    while (n > 1) {12      if (k > n / 2) {13        k -= n / 2;14        d += operations[i - 1];15      }16      n /= 2;17      --i;18    }19    return 'a' + (d % 26);20  }21};

1class Solution:2    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"))

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 problem

Solution

1class Solution {2public3  char kthCharacter(long k, int[] operations) {4    long n = 1;5    int i = 0;6    while (n < k) {7      n *= 2;8      ++i;9    }10    int d = 0;11    while (n > 1) {12      if (k > n / 2) {13        k -= n / 2;14        d += operations[i - 1];15      }16      n /= 2;17      --i;18    }19    return (char)('a' + (d % 26));20  }21}

1class Solution {2public:3  char kthCharacter(long long k, vector<int> &operations) {4    long long n = 1;5    int i = 0;6    while (n < k) {7      n *= 2;8      ++i;9    }10    int d = 0;11    while (n > 1) {12      if (k > n / 2) {13        k -= n / 2;14        d += operations[i - 1];15      }16      n /= 2;17      --i;18    }19    return 'a' + (d % 26);20  }21};

1class Solution:2    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"))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.