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

The problem describes a string manipulation game between Alice and Bob. Initially, Alice starts with a string word = "a". Bob provides a list of operations, represented by the integer array operations.

leetcodehardmathbit-manipulationrecursion

LeetCode Problem 3307

Difficulty: 🔴 Hard
Topics: Math, Bit Manipulation, Recursion

Solution

Problem Understanding

The problem describes a string manipulation game between Alice and Bob. Initially, Alice starts with a string word = "a". Bob provides a list of operations, represented by the integer array operations. Each operation transforms word in a specific way:

  • If operations[i] == 0, Alice duplicates the current string by appending a copy of it to itself.
  • If operations[i] == 1, Alice generates a new string by incrementing every character in word to its next letter in the alphabet (with 'z' wrapping around to 'a') and appends this new string to the original word.

The goal is to determine the k-th character of the final string after performing all operations in sequence.

The constraints indicate that k can be extremely large (up to 10^14), and the number of operations is modest (≤100). This immediately implies that constructing the string explicitly is infeasible due to both memory and time limitations. The problem guarantees that after performing all operations, the string is at least k characters long, so we do not need to handle out-of-bounds k.

Important edge cases include very large k values with sequences of only doubling operations, operations that wrap 'z' to 'a', and sequences mixing both operations repeatedly. These edge cases could break naive approaches if the algorithm tries to materialize the full string.

Approaches

The brute-force approach is straightforward: simulate all operations on the string step by step. For each operation, either append a copy of the string (for 0) or generate the incremented string and append it (for 1). After all operations, return the k-th character. While this works correctly for small inputs, it is impractical for large k because the string grows exponentially, potentially exceeding 10^14 characters.

The optimal approach leverages the observation that we do not need the entire string; we only need to determine the character at position k. We can compute the length of the string after each operation recursively or iteratively and then reverse-engineer which part of the string contributed the k-th character. For a doubling operation, the string is repeated, so the character at k may belong to the first or second half. For an increment operation, the character may belong to the original string or the incremented version, in which case we need to adjust for the character shift. By recursively tracing back through the operations, we can determine the k-th character without constructing the full string.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(2^n) Explicitly builds the string; infeasible for large k
Optimal O(n) O(n) Uses length tracking and recursive backtracking to find k-th character

Algorithm Walkthrough

  1. Compute final lengths: Initialize a list of lengths corresponding to the string length after each operation. Start with length[0] = 1 for the initial string "a". For each operation, update the length:
  • If op == 0, length[i] = length[i-1] * 2.
  • If op == 1, length[i] = length[i-1] * 2.

Note that both operations double the string length, but type 1 changes the characters in the second half. 2. Trace back the k-th character: Starting from the last operation and current k, check which segment k belongs to:

  • For op == 0:

  • If k <= length[i-1], recurse into the first half.

  • Otherwise, subtract length[i-1] from k and recurse into the second half.

  • For op == 1:

  • If k <= length[i-1], recurse into the first half with no change.

  • Otherwise, subtract length[i-1] from k, recurse into the original first half, and increment the character by 1 (wrap 'z' to 'a').

  1. Base case: When all operations have been traced back, return the initial character "a".

Why it works: The algorithm maintains the invariant that at each step, we know the range of characters contributed by each segment. By recursively identifying which segment contains the k-th character and adjusting for character increments, we avoid materializing the full string. Each operation is considered once, so the solution runs in O(n).

Python Solution

from typing import List

class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        n = len(operations)
        lengths = [1]  # initial length of "a"
        
        # Precompute lengths after each operation
        for i in range(n):
            lengths.append(lengths[-1] * 2)
        
        def dfs(op_idx: int, k: int, increment: int) -> str:
            if op_idx == 0:
                # Base case: the initial character "a" with accumulated increment
                return chr((ord('a') - ord('a') + increment) % 26 + ord('a'))
            
            op = operations[op_idx - 1]
            half_len = lengths[op_idx - 1]
            
            if k <= half_len:
                return dfs(op_idx - 1, k, increment)
            else:
                if op == 0:
                    return dfs(op_idx - 1, k - half_len, increment)
                else:
                    return dfs(op_idx - 1, k - half_len, (increment + 1) % 26)
        
        return dfs(n, k, 0)

The Python implementation first computes the lengths of the string after each operation. It then uses a recursive function dfs to trace back the k-th character. The increment parameter tracks how many times a character should be shifted forward due to type 1 operations. The base case is the initial "a" character with modulo arithmetic to wrap 'z' to 'a'.

Go Solution

func kthCharacter(k int64, operations []int) byte {
    n := len(operations)
    lengths := make([]int64, n+1)
    lengths[0] = 1
    
    // Precompute lengths after each operation
    for i := 0; i < n; i++ {
        lengths[i+1] = lengths[i] * 2
    }
    
    var dfs func(opIdx int, k int64, increment int) byte
    dfs = func(opIdx int, k int64, increment int) byte {
        if opIdx == 0 {
            return byte((('a' - 'a' + byte(increment)) % 26) + 'a')
        }
        op := operations[opIdx-1]
        halfLen := lengths[opIdx-1]
        
        if k <= halfLen {
            return dfs(opIdx-1, k, increment)
        } else {
            if op == 0 {
                return dfs(opIdx-1, k-halfLen, increment)
            } else {
                return dfs(opIdx-1, k-halfLen, (increment+1)%26)
            }
        }
    }
    
    return dfs(n, k, 0)
}

In Go, we use slices for the lengths array and a recursive closure dfs to perform the backtracking. The character increment is handled modulo 26 to wrap 'z' to 'a'. Go requires explicit type casting for arithmetic on bytes.

Worked Examples

Example 1: k = 5, operations = [0,0,0]

Step Operation String Length Segment containing k=5
0 - 1 Base "a"
1 0 2 k=5 > 1 → second half
2 0 4 k=3 > 2 → second half
3 0 8 k=1 → recurse to base

Result: "a"

Example 2: k = 10, operations = [0,1,0,1]

Step Operation Length k Segment Increment
0 - 1 - 0
1 0 2 k=10 → second half 0
2 1 4 k=8 → second half +1
3 0 8 k=4 → first half 1
4 1 16 k=4 → first half 1

Result: "b"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each operation is considered once during the backtracking.
Space O(n) Storing lengths array of size n+1 and recursion stack up to n.

Because we avoid constructing the string, the algorithm is feasible even for k as large as 10^14.

Test Cases

# Provided examples
assert Solution().kthCharacter(5, [0,0,0]) == "a"  # all doubling
assert Solution