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:
operations[i] == 0, append a copy of word to itself.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:
"a" to "a", word becomes "aa"."aa" to "aa", word becomes "aaaa"."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:
"a" to "a", word becomes "aa"."bb" to "aa", word becomes "aabb"."aabb" to "aabb", word becomes "aabbaabb"."bbccbbcc" to "aabbaabb", word becomes "aabbaabbbbccbbcc".
Constraints:
1 <= k <= 10141 <= operations.length <= 100operations[i] is either 0 or 1.word has at least k characters after all operations.This approach involves simulating the operations but focuses on efficiently calculating the length of the string after each operation, instead of building the entire string. This is feasible due to the rapidly increasing length after each operation.
As we iterate through the operations, keep track of the length of the string after each operation is performed. Instead of growing the string, calculate what the length would be, tracking this incrementally.
Once the total length is known, locate where the k-th character is within the operations' results using the calculated lengths.
This Python solution efficiently calculates the length of the string after each operation, without constructing the string. By maintaining the growing length, it determines the segment in which the k-th character resides, and then backtracks through the operations to locate and identify the character.
C++
Java
C#
JavaScript
Time Complexity: O(n) where n is the number of operations because we iterate over the operations twice.
Space Complexity: O(1) since storing a few integer variables only.
Rather than directly growing or calculating the full length, consider a recursive approach to track what operation modifies length.
By recursively reducing the operations and finding length, the k-th index can be tracked back through recursive reductions.
The approach considers whether each operation, when halved recursively, results in a k that is larger or smaller than the halved length and adjusts recursively.
A recursive Python solution utilizing recursion to continuously reduce operations and determine where the kth falls in reduced-size operations. This avoids generating the string by finding length recursively.
C++
Java
C#
JavaScript
Time Complexity: O(n), similar to iterative solution due to recursion depth.
Space Complexity: O(n) for recursion depth.
| Approach | Complexity |
|---|---|
| Approach 1: Simulate Operations with Direct Calculation | Time Complexity: O(n) where n is the number of operations because we iterate over the operations twice. |
| Approach 2: Recursive Length Calculation with Reduction | Time Complexity: O(n), similar to iterative solution due to recursion depth. |
❌ Don't Run Behind 500 LEETCODE Problems ❌ Focus on QPCD • Striver • 522,282 views views
Watch 9 more video solutions →Practice Find the K-th Character in String Game II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor