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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the K-th Character in String Game I

Number: 3600

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Alice starts with the string "a". In each operation, she creates a new string by changing every character in the current string to its next character in the alphabet (with 'z' cycling back to 'a') and then appends this new string to the original. After performing this operation repeatedly, we obtain a string that doubles in length each time. Given a positive integer k (1 <= k <= 500), the task is to determine the k-th character (1-indexed) in the infinitely generated string once it is long enough.

Key Insights

  • The string is constructed by repeatedly doubling its length, where the second half is a transformed version (by shifting letters) of the first.
  • Instead of constructing the entire string (which grows exponentially), we can use recursion to determine the character directly.
  • Let f(n) be the string after n operations. Then f(n+1) = f(n) + transform(f(n)), with length 2^(n+1).
  • The k-th character can be found by determining whether it is in the first half (same as f(n)) or second half (transformed character from f(n)).
  • A recursive approach reduces the problem size by half at each step, leading to a O(log k) time complexity.

Space and Time Complexity

Time Complexity: O(log k) – the recursion depth is proportional to the number of operations needed (roughly log2(k)). Space Complexity: O(log k) – due to the recursion call stack.

Solution

We solve the problem by first noting that after n operations, the string length is 2^n. We find the minimal n such that 2^n >= k. Then, we recursively determine the k-th character:

  1. Base case: When no operation is performed (n = 0), the only character is "a".
  2. Otherwise, if k is in the first half of the string generated at step n, then the answer is the same as the k-th character from step n-1.
  3. If k is in the second half, then it corresponds to the (k - 2^(n-1))-th character from the previous version, and we apply the transformation (shift to the next character, with 'z' wrapping to 'a').

We use recursion to compute the answer without constructing the entire string.

Code Solutions

# Python solution using recursion.

def findKthCharacter(k: int) -> str:
    # Helper function to perform character shift with wrap-around.
    def transform(ch: str) -> str:
        # If character is 'z', wrap around to 'a'
        return 'a' if ch == 'z' else chr(ord(ch) + 1)
    
    # Recursive function that returns the kth character after n operations,
    # where 2^n is the length of the current string.
    def kthChar(n: int, k: int) -> str:
        if n == 0:
            return 'a'
        # halfLength corresponds to the length of the string before the last operation.
        halfLength = 1 << (n - 1)
        if k <= halfLength:
            # k-th character falls in the first half; recursion continues in the same manner.
            return kthChar(n - 1, k)
        else:
            # k-th character falls in the second half; get the corresponding character from the first half 
            # and apply transformation.
            return transform(kthChar(n - 1, k - halfLength))
    
    # Determine the minimum number of operations such that the string length is at least k.
    n = 0
    while (1 << n) < k:
        n += 1
    return kthChar(n, k)

# Example usage:
print(findKthCharacter(5))   # Expected output: "b"
print(findKthCharacter(10))  # Expected output: "c"
← Back to All Questions