LeetCode Solutions Blog

Find the K-th Character in String Game I

Difficulty: Easy

Problem Description

Alice starts with a string word = "a". Bob will ask Alice to repeatedly generate a new string by changing each character in word to its next character in the English alphabet and appending it to the original word. The task is to find the k-th character in word after enough operations have been done so that word has at least k characters.

Key Insights

The string grows exponentially with each operation.
Each character in the string cycles through the alphabet (i.e., 'z' changes to 'a').
We can determine the k-th character without generating the entire string by understanding the growth pattern.
The string length after n operations is 2^n.

Space and Time Complexity

Time Complexity: O(log k)
Space Complexity: O(1)

Solution

To solve the problem, we can use the following approach:

Determine how many operations are needed for the length of the string to reach or exceed k.
Calculate the length of the string after each operation, which doubles with each iteration (i.e., 1, 2, 4, 8,...).
Once the necessary operation count is found, backtrack to find the specific character corresponding to k using the properties of the string transformation.
Use modular arithmetic to find the character's position in the original string.

Code Solutions

def findKthCharacter(k):
    # Initialize the current string length and operation count
    length = 1
    operations = 0
    
    # Determine how many operations are needed for the string length to reach or exceed k
    while length < k:
        operations += 1
        length = 2 * length  # The length doubles with each operation
    
    # Backtrack to find the k-th character
    while operations > 0:
        # Find the length of the previous string
        prev_length = length // 2
        
        if k > prev_length:
            # If k is in the new part, find its corresponding character in the original string
            k = k - prev_length  # Adjust k to find its position in the original string
            k = (k - 1) % 26 + 1  # Map to the character in the alphabet (1-indexed)
            break
        else:
            # If k is in the original part, we just need to backtrack
            length = prev_length
        
        operations -= 1
    
    # Convert k to the corresponding character
    return chr(ord('a') + (k - 1))  # Convert 1-indexed to 0-indexed character

# Example usage
print(findKthCharacter(5))  # Output: "b"
print(findKthCharacter(10)) # Output: "c"