3307. Find the K-th Character in String Game II

HardBit ManipulationRecursionMath

Problem Description

Alice and Bob are playing a game. Initially, Alice has a string word = "a". You are given a positive integer k. You are also provided with an integer array operations, where operations[i] represents the type of the i-th operation. 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.

Intuition

The key observation for this problem is that the length of the string doubles with each operation performed. If we consider i operations, the length of the string will be 2^i. Given this property of doubling with operations, we can simulate the process to determine the smallest string length n that is greater than or equal to k.

Once the necessary string length is found, we backtrack to determine the k-th character by considering two cases:

If k > n / 2, it indicates that k is in the second half of the string formed after doubling. In this case, if operations[i - 1] was 1, the character for the k-th position is derived by adding 1 to the character in the first half. We update k to k - n / 2.
If k <= n / 2, it implies that k is in the first half and thus not influenced by the latest operation.

By iterating and halving the length n until n = 1, we determine the effect of operations to find the correct character. The resulting character is derived by converting the accumulated transformation value to a character using modulo 26 and adding it to the ASCII value of 'a'.

Learn more about Recursion and Math patterns.

Solution Approach

To solve the problem, we need to identify the character at the k-th position after performing a series of operations that either double the string or increment each character:

Identify String Length: First, determine the minimal length n required such that n is greater than or equal to k. This step involves repeatedly doubling n while keeping track of the number of operations.
Backtracking through Operations:
- We backtrack to figure out how the operations affect the position of k in the final string configuration.
- We start from the largest string segment found earlier and progressively reduce it, determining if k lies in the first or second half.
Determine Position Impact:
- If k > n / 2, adjust k by subtracting n / 2 and consider if the operation was of type 1. If so, increment the character count to account for the change to the next alphabet character.
- If k <= n / 2, the impact is negligible as k remains in the original segment.
Final Calculation:
- By continuing to reduce n until it equals 1, we zero in on the impact of each operation on the final position of k.
- The operation impact (number of increments) is consolidated into the variable d, representing any shift in character.
Determine Character and Return:
- Calculate the resultant character by using the modulo operation: chr(d % 26 + ord("a")), which gives the final character in the alphabet after applying all transformations.

This systematic approach allows us to efficiently determine the character without forming large strings explicitly, using mathematical reasoning to deduce the effect of operations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example to illustrate the approach:

Suppose we have k = 5 and operations = [1, 0, 1].

Initially, Alice has the word = "a".

First Operation (operations[0] == 1):
- Transform "a" to its next character "b", and append: "a" + "b" = "ab".
- word is now "ab".
Second Operation (operations[1] == 0):
- Append a copy of word to itself: "ab" + "ab" = "abab".
- word is now "abab".
Third Operation (operations[2] == 1):
- Transform each character in "abab" to its next character and append it to the original word.
- "a" becomes "b" and "b" becomes "c", therefore: "abab" + "bcbc" = "ababbcbc".
- word is now "ababbcbc".

Now, word has length 8, and we are interested in the character at the 5-th position (1-based index), which is "b".

Following the Solution Approach:

Identify String Length:
- After performing the operations, we observe that word length = 8 is greater than k = 5.
Backtracking through Operations:
- We start with n = 8, where k = 5 falls into the second half of "abab" + "bcbc".
Determine Position Impact:
- Since k > n / 2 (5 > 4), update k = 5 - 4 = 1, and note that operations[2] = 1 was applied here, hence adjust for the character shift.
- In the second half "bcbc", at position 1, the character is derived from transforming the first half, so we shift "a" to "b".
Final Calculation:
- Continue with n reduction until we find that the initial word from which the 5-th character derives was "a".
- The 5-th character in the final string is "b" after considering the transformations.
Determine Character and Return:
- The impact of operations results in finding 'b' as the character using chr((d + ord("a")) % 26).

Thus, the character at the k-th position after performing all operations is 'b'.

Solution Implementation

1from typing import List
2
3class Solution:
4    def kthCharacter(self, k: int, operations: List[int]) -> str:
5        # Initialize n to represent the smallest power of 2 greater than or equal to k
6        n, i = 1, 0
7      
8        # Determine the smallest power of 2 greater than or equal to k
9        # Also, find the index i which denotes the number of operations
10        while n < k:
11            n *= 2
12            i += 1
13      
14        # Initialize the total change in character (d)
15        d = 0
16
17        # Traverse back down to determine the correct character based on k
18        while n > 1:
19            # If k is in the second half, adjust k and increase d by the operation value
20            if k > n // 2:
21                k -= n // 2
22                d += operations[i - 1]
23            # Reduce n to the next smaller power of 2
24            n //= 2
25            # Decrease i to move to the next previous operation in the list
26            i -= 1
27      
28        # Convert the final computed value to a character from a-z
29        return chr(d % 26 + ord("a"))
30

1class Solution {
2    public char kthCharacter(long k, int[] operations) {
3        // Initialize n to 1. It keeps track of the length of the current sequence.
4        long n = 1;
5        // i keeps track of the number of operations performed to reach the current n.
6        int i = 0;
7
8        // Loop to find the smallest n that is greater than or equal to k.
9        while (n < k) {
10            n *= 2; // Double n to simulate the sequence expansion.
11            i++; // Increment i to match the number of doublings.
12        }
13
14        // Initialize d to 0. It represents the total adjustment from operations.
15        int d = 0;
16
17        // While n is greater than 1, adjust k and d according to the sequence's behavior.
18        while (n > 1) {
19            // Check if k falls in the second half of the current sequence.
20            if (k > n / 2) {
21                k -= n / 2; // Adjust k to map onto the second half.
22                d += operations[i - 1]; // Apply the corresponding operation adjustment.
23            }
24            n /= 2; // Halve n to simulate reducing the sequence to a prior state.
25            i--; // Decrement i to backtrack in operations array.
26        }
27
28        // Compute the character by adjusting 'a' with the accumulated operation modifications.
29        return (char) ('a' + (d % 26));
30    }
31}
32

1#include <vector>
2
3class Solution {
4public:
5    char kthCharacter(long long k, std::vector<int>& operations) {
6        long long powerOfTwo = 1; // Initialize powerOfTwo as 2^0
7        int index = 0; // Initialize index for operations vector
8
9        // Find the smallest power of 2 greater than or equal to k
10        while (powerOfTwo < k) {
11            powerOfTwo *= 2;
12            ++index;
13        }
14
15        int cumulativeShift = 0; // Initialize cumulativeShift to track operations
16
17        // Work backwards to determine the character position modifications
18        while (powerOfTwo > 1) {
19            if (k > powerOfTwo / 2) {
20                k -= powerOfTwo / 2; // Adjust k for the second half of current range
21                cumulativeShift += operations[index - 1]; // Apply corresponding operation
22            }
23            powerOfTwo /= 2; // Move to the next smaller range
24            --index; // Adjust index to track operations correctly
25        }
26
27        // Calculate the character and return it
28        return 'a' + (cumulativeShift % 26);
29    }
30};
31

1// Function to find the k-th character in a transformed sequence
2function kthCharacter(k: number, operations: number[]): string {
3    let n = 1; // Initialize the length of the sequence
4    let i = 0; // Initialize the operation index
5
6    // Determine the length of the sequence that contains the k-th character
7    while (n < k) {
8        n *= 2; // Double the length of the sequence
9        i++;    // Increment the operation index
10    }
11
12    let d = 0; // Initialize the cumulative operation effect
13
14    // Traverse down to the k-th character, adjusting k and d accordingly
15    while (n > 1) {
16        if (k > n / 2) {
17            k -= n / 2;              // Adjust k to reflect the second half of the sequence
18            d += operations[i - 1];  // Add the current operation effect
19        }
20        n /= 2;  // Halve the size of the current sequence
21        i--;     // Decrement the operation index
22    }
23
24    // Calculate the resultant character by applying modulo 26 on the total operation effect
25    return String.fromCharCode('a'.charCodeAt(0) + (d % 26));
26}
27

Time and Space Complexity

The time complexity is O(log k), which results from the doubling process to find the smallest power of two greater than or equal to k. Each step in the while loop approximately halves n, leading to logarithmic complexity relative to k. The space complexity is O(1), as the algorithm uses a constant amount of space regardless of input size, primarily for variables n, i, d, and k.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don’t know