Find the K-th Character in String Game II

Hard

Asked by:

5 views

Topics:

ArraysStrings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The problem refers to the 'k-th' character. Should I assume this is 1-based indexing or 0-based indexing?
Given that `k` can be as large as 10^14, should I plan on using a 64-bit integer type to store its value?
To clarify the type 1 operation, is the 'next character' transformation equivalent to a modular increment on the character's 0-25 alphabetic index, ensuring 'z' correctly wraps around to 'a'?
Is the initial string `word = "a"` a fixed starting condition for all test cases, or could it vary?
The problem guarantees that the final string will have at least `k` characters. For completeness, what would be the expected behavior if `k` were larger than the final string's length?

Brute Force Solution

Approach

The most direct way to solve this is to actually play the game round by round, building the entire sequence of characters. Once we have the final, complete sequence after all rounds are finished, we can simply go to the requested spot and see what character is there.

Here's how the algorithm would work step-by-step:

Start with the very first character the game gives you.
Now, to get the sequence for the next round, we'll create a new, empty sequence.
Go through the current sequence one character at a time from beginning to end.
For each character, find the new piece of sequence it transforms into according to the game's rules.
Add this new piece to the end of the new sequence we are building.
Once you've done this for all characters in the old sequence, the new sequence is complete. This becomes your current sequence for the next round.
Repeat this entire process of building a new sequence from the old one for the specified number of rounds.
After all rounds are done, you'll have one final, very long sequence of characters.
Finally, count from the start of this final sequence to the exact position you're interested in and read the character at that spot.

Code Implementation

def find_kth_character_brute_force(initial_character, rules, rounds, kth_index):
    current_string = initial_character

    # Simulate the string generation process for the specified number of rounds.
    for round_number in range(rounds):
        
        next_string_parts = []
        # Build the next version of the string by transforming each character from the current version.
        for character_to_transform in current_string:
            
            transformation_result = rules[character_to_transform]
            # Append the result of the transformation to form the next generation string.
            next_string_parts.append(transformation_result)
            
        current_string = "".join(next_string_parts)

    # After all rounds, the final string is built, so we can access the k-th character directly.
    # The problem uses 1-based indexing, so we subtract 1 for the 0-based string index.
    return current_string[kth_index - 1]

Big(O) Analysis

Time Complexity

O(2^n) – The cost is driven by building the string, whose length grows exponentially with the number of rounds, n. If each character expands into two characters, the string's length doubles at each of the n rounds. The total number of character operations is the sum of the string lengths at each step, which forms a geometric series (e.g., 1 + 2 + 4 + ... + 2^(n-1)). This series sums to approximately 2^n, giving a final time complexity of O(2^n).

Space Complexity

O(N) – The primary memory usage comes from explicitly constructing the character sequence for each round as described. The algorithm builds a "new sequence" that grows with each iteration until it becomes the "final, complete sequence" after all rounds are finished. This final string is stored in its entirety in order to access the requested character at the K-th position. Therefore, if we define N as the length of this final sequence, the auxiliary space required is directly proportional to N.

Optimal Solution

Approach

The key is to avoid building the massive final string, which would be too slow and use too much memory. Instead, we can deduce the single character we need by tracing its origin backward, step by step, all the way to the initial character.

Here's how the algorithm would work step-by-step:

Think about the character you want to find. It was created in the final step from a 'parent' character in the step just before.
First, figure out which parent is responsible. Since each parent character expands into a small, fixed-size block of new characters, you can tell which block your target position falls into. This identifies the parent's position in the previous string.
Next, determine if your target was the first, second, etc., character created by that parent. This is found simply by seeing where your position lies within its little block.
Now, you have a new goal: find out what that parent character was. To do this, you repeat the exact same process for the parent, finding its own parent one step earlier.
Continue this journey backward, finding the ancestor at each preceding step. The position you're looking for will get smaller and smaller.
Eventually, your journey will end at the very first step, where the string consists of a single, known character, which is the ultimate ancestor.
Finally, replay the journey forward. Using the known starting character and the sequence of choices you noted on your way back, you can apply the expansion rules step-by-step to reveal the character at each stage, until you arrive at the final answer.

Code Implementation

def find_kth_character_in_game(string_level_n, position_k):
    flip_counter = 0
    current_string_length = 1 << (string_level_n - 1)

    # We repeatedly halve the problem by tracing the position back to its origin in the base string.

    while current_string_length > 1:
        midpoint_position = current_string_length // 2

        # This is the key decision: is the position in the original half or the generated, flipped half?

        if position_k > midpoint_position:
            flip_counter += 1
            position_k = position_k - midpoint_position
        
        current_string_length = current_string_length // 2

    # The final character depends on the parity of flips encountered on the path to the base case.

    if flip_counter % 2 == 0:
        return 'a'
    else:
        return 'b'

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the number of expansion steps, n, as the algorithm does not build the string. The process involves first tracing the character's origin backward from step n to step 1, which consists of a loop that runs n times with constant-time arithmetic inside. Then, it replays the generation forward from step 1 to n, also a loop of n iterations with constant-time rule application at each step. The total operations are directly proportional to n from the backward pass plus n from the forward pass, which simplifies to O(n).

Space Complexity

O(N) – The algorithm traces the character's origin backward from the final step N down to the initial step. This backward traversal is naturally implemented with recursion, where each call represents one step back in time. This process results in a call stack with a maximum depth of N, as there is one recursive call for each of the N steps in the game. Since each stack frame stores a constant number of variables, the auxiliary space is determined by this maximum recursion depth.

Edge Cases

Case	How to Handle
The value of k is close to the maximum constraint of 10^14.	The solution must use 64-bit integer types for k and intermediate length calculations to prevent numerical overflow.
The number of operations is large, causing intermediate lengths (2^i) to exceed 64-bit integer limits.	The algorithm implicitly handles this as any length that would overflow a 64-bit integer is guaranteed to be greater than k.
The value of k is 1.	The backward reduction algorithm correctly determines that k is always in the first half of the string, resulting in zero transformations and the answer 'a'.
The operations array contains only type 0 (duplication) operations.	The solution correctly computes a total transformation count of zero since the condition for incrementing it is never met, returning 'a'.
The total number of character transformations is 26 or more.	The final character calculation uses a modulo 26 operation on the total transformation count to correctly handle wrapping around the alphabet.
The value of k is exactly a power of two, which falls on a boundary.	Using a strict inequality (e.g., k > length/2) correctly places this boundary index in the first half of the string, preventing an off-by-one error.
A small k value is combined with a large number of operations.	The backward-working solution is efficient because for most steps, k will be in the first half, requiring no modification to k or the transform count.
The final length of the word is much larger than k.	The solution does not need to compute the full final length, as it works backward from a point determined by the number of operations.

The value of k is close to the maximum constraint of 10^14.

How to Handle:

The solution must use 64-bit integer types for k and intermediate length calculations to prevent numerical overflow.

The number of operations is large, causing intermediate lengths (2^i) to exceed 64-bit integer limits.

How to Handle:

The algorithm implicitly handles this as any length that would overflow a 64-bit integer is guaranteed to be greater than k.

The value of k is 1.

How to Handle:

The backward reduction algorithm correctly determines that k is always in the first half of the string, resulting in zero transformations and the answer 'a'.

The operations array contains only type 0 (duplication) operations.

How to Handle:

The solution correctly computes a total transformation count of zero since the condition for incrementing it is never met, returning 'a'.

The total number of character transformations is 26 or more.

How to Handle:

The final character calculation uses a modulo 26 operation on the total transformation count to correctly handle wrapping around the alphabet.

The value of k is exactly a power of two, which falls on a boundary.

How to Handle:

Using a strict inequality (e.g., k > length/2) correctly places this boundary index in the first half of the string, preventing an off-by-one error.

A small k value is combined with a large number of operations.

How to Handle:

The backward-working solution is efficient because for most steps, k will be in the first half, requiring no modification to k or the transform count.

The final length of the word is much larger than k.

How to Handle:

The solution does not need to compute the full final length, as it works backward from a point determined by the number of operations.