K-th Character in String Game II

Problem Description

Alice and Bob are playing a game. Initially, Alice has a string word = "a".

Operation 0: Append a copy of word to itself

Operation 1: Generate new string by changing each character to its next character, then append

Algorithm Explanation

Initialize

Start with word = "a"

Process Operations

For each operation, either duplicate (0) or transform and append (1)

Find K-th Character

Return the character at position k (1-indexed)

Time Complexity

O(n)

Where n is the number of operations

Space Complexity

O(1)

Optimized approach uses constant extra space

Mathematical Optimization

For large k values, we use bit manipulation and mathematical properties to avoid generating the entire string.

// Optimized approach for large k
function findKthCharacter(k, operations) {
    // Use mathematical properties
    // Track position and increments
    // Avoid string generation
}

Examples

Example 1

Easy

Input: k = 5, operations = [0,0,0]

Output: "a"

Example 2

Medium

Input: k = 10, operations = [0,1,0,1]

Output: "b"

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