04_Find_the_K-th_Character_in_String_Game_II.cpp

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

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

class Solution
{
public:
    char kthCharacter(long long k, vector<int> &operations)
    {
        int shift = 0;
        vector<long long> lengths;
        long long len = 1;

        for (int op : operations)
        {
            len *= 2;
            lengths.push_back(len);
            if (len >= k)
                break;
        }

        for (int i = lengths.size() - 1; i >= 0; --i)
        {
            long long half = lengths[i] / 2;
            int op = operations[i];
            if (k > half)
            {
                k -= half;
                if (op == 1)
                    shift++;
            }
        }

        return (char)((('a' - 'a' + shift) % 26) + 'a');
    }
};

/*
Code Explanation:
This solution efficiently finds the kth character in a string after performing a series of operations without actually generating the entire string.

1. First loop:
   - Calculates lengths after each operation (doubling each time)
   - Stores these lengths in a vector
   - Stops when length exceeds k to avoid unnecessary calculations

2. Second loop:
   - Works backwards through the operations
   - For each operation, determines if k falls in first or second half
   - If k is in second half, adjusts k and tracks character shifts

3. Final calculation:
   - Uses accumulated shifts to determine final character
   - Handles wraparound from 'z' to 'a' using modulo

Time Complexity: O(min(N, log k)) where N is length of operations array
Space Complexity: O(min(N, log k)) for storing lengths vector

The solution avoids generating the actual string, making it memory efficient for large inputs.
*/