We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the K-th Character in String Game II

Difficulty: Hard

Problem Description

Alice and Bob are playing a game where Alice starts with the string "a" and performs a series of operations based on the input. The operations can either append a copy of the string to itself or change each character to its next character in the English alphabet and append it to the original string. The goal is to determine the k-th character in the resulting string after all operations are performed.

Key Insights

  • The operations can drastically increase the length of the string, making direct simulation infeasible for large k.
  • Each operation has a predictable effect on the length of the string, which can be calculated without generating the entire string.
  • The transformation of characters in operation type 1 needs to be tracked efficiently without generating new strings.

Space and Time Complexity

Time Complexity: O(n), where n is the number of operations due to the need to traverse the list of operations once. Space Complexity: O(1), since we only store a few variables to track lengths and current character transformations.

Solution

To solve this problem, we can avoid generating the entire string by tracking the lengths of the string after each operation. We start with an initial length of 1 (for the string "a"). For each operation:

  1. If the operation is of type 0, the length doubles.
  2. If the operation is of type 1, we append a transformed version of the string, effectively increasing the length by the original length.

After processing all operations, we can calculate the final length of the string. To find the k-th character, we can backtrack through the operations to identify which character corresponds to the index k.

Code Solutions

def findKthCharacter(k, operations):
    length = 1  # initial length of "a"
    
    # Calculate the length after each operation
    for op in operations:
        if op == 0:
            length *= 2
        else:  # op == 1
            length = length * 2 + length
    
    # Now we need to backtrack to find the k-th character
    for op in reversed(operations):
        if k > length:
            return ''  # this case should not happen according to constraints
        if op == 0:
            length //= 2
        else:  # op == 1
            if k > length // 2:
                k = k - (length // 2)  # move to the second half
                k = (k - 1) % length + 1  # find the position in the transformed part
            length //= 2
    
    # Finally, we need to determine the character at index k
    return chr(ord('a') + (k - 1) % 26)
← Back to All Questions