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

SourceWeekly Contest 417 Q4DifficultyHardRating2232

Description

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

You are given a positive integer k. You are also given an integer array operations, where operations[i] represents the type of the i^th operation.

Now Bob will ask Alice to perform all operations in sequence:

If operations[i] == 0, append a copy of word to itself.
If operations[i] == 1, generate a new string by changing each character in word to its next character in the English alphabet, and append it to the original word. For example, performing the operation on "c" generates "cd" and performing the operation on "zb" generates "zbac".

Return the value of the k^th character in word after performing all the operations.

Note that the character 'z' can be changed to 'a' in the second type of operation.

Example 1:

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

Output: "a"

Explanation:

Initially, word == "a". Alice performs the three operations as follows:

Appends "a" to "a", word becomes "aa".
Appends "aa" to "aa", word becomes "aaaa".
Appends "aaaa" to "aaaa", word becomes "aaaaaaaa".

Example 2:

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

Output: "b"

Explanation:

Initially, word == "a". Alice performs the four operations as follows:

Appends "a" to "a", word becomes "aa".
Appends "bb" to "aa", word becomes "aabb".
Appends "aabb" to "aabb", word becomes "aabbaabb".
Appends "bbccbbcc" to "aabbaabb", word becomes "aabbaabbbbccbbcc".

Constraints:

1 <= k <= 10¹⁴
1 <= operations.length <= 100
operations[i] is either 0 or 1.
The input is generated such that word has at least k characters after all operations.

Solutions

Solution 1: Recurrence

Thinking

With \(k \le 10^{14}\) we cannot build the string as in part I. Each operation doubles the length, so the \(k\)-th character is determined by a chain of “shift or not” decisions.

Find the first length \(n=2^i\) that is at least \(k\), then walk the operations backward. If \(k\) lies in the second half, it comes from the matching first-half index and we add \(1\) when \(\textit{operations}[i-1]=1\), then map \(k\) back to the first half.

When the length becomes \(1\), the accumulated shift modulo \(26\) is the letter. The walk takes \(O(\log k)\) steps.

Since the length of the string doubles after each operation, if we perform \(i\) operations, the length of the string will be \(2^i\).

We can simulate this process to find the first string length \(n\) that is greater than or equal to \(k\).

Next, we backtrack and discuss the following cases:

If \(k \gt n / 2\), it means \(k\) is in the second half. If \(\textit{operations}[i - 1] = 1\), it means the character at position \(k\) is obtained by adding \(1\) to the character in the first half. We add \(1\) to it. Then we update \(k\) to \(k - n / 2\).
If \(k \le n / 2\), it means \(k\) is in the first half and is not affected by \(\textit{operations}[i - 1]\).
Next, we update \(n\) to \(n / 2\) and continue backtracking until \(n = 1\).

Finally, we take the resulting number modulo \(26\) and add the ASCII code of 'a' to get the answer.

The time complexity is \(O(\log k)\), and the space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRustC#PHP

class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        n, i = 1, 0
        while n < k:
            n *= 2
            i += 1
        d = 0
        while n > 1:
            if k > n // 2:
                k -= n // 2
                d += operations[i - 1]
            n //= 2
            i -= 1
        return chr(d % 26 + ord("a"))

class Solution {
    public char kthCharacter(long k, int[] operations) {
        long n = 1;
        int i = 0;
        while (n < k) {
            n *= 2;
            ++i;
        }
        int d = 0;
        while (n > 1) {
            if (k > n / 2) {
                k -= n / 2;
                d += operations[i - 1];
            }
            n /= 2;
            --i;
        }
        return (char) ('a' + (d % 26));
    }
}

class Solution {
public:
    char kthCharacter(long long k, vector<int>& operations) {
        long long n = 1;
        int i = 0;
        while (n < k) {
            n *= 2;
            ++i;
        }
        int d = 0;
        while (n > 1) {
            if (k > n / 2) {
                k -= n / 2;
                d += operations[i - 1];
            }
            n /= 2;
            --i;
        }
        return 'a' + (d % 26);
    }
};

func kthCharacter(k int64, operations []int) byte {
    n := int64(1)
    i := 0
    for n < k {
        n *= 2
        i++
    }
    d := 0
    for n > 1 {
        if k > n/2 {
            k -= n / 2
            d += operations[i-1]
        }
        n /= 2
        i--
    }
    return byte('a' + (d % 26))
}

function kthCharacter(k: number, operations: number[]): string {
    let n = 1;
    let i = 0;
    while (n < k) {
        n *= 2;
        i++;
    }
    let d = 0;
    while (n > 1) {
        if (k > n / 2) {
            k -= n / 2;
            d += operations[i - 1];
        }
        n /= 2;
        i--;
    }
    return String.fromCharCode('a'.charCodeAt(0) + (d % 26));
}

impl Solution {
    pub fn kth_character(mut k: i64, operations: Vec<i32>) -> char {
        let mut n = 1i64;
        let mut i = 0;
        while n < k {
            n *= 2;
            i += 1;
        }
        let mut d = 0;
        while n > 1 {
            if k > n / 2 {
                k -= n / 2;
                d += operations[i - 1] as i64;
            }
            n /= 2;
            i -= 1;
        }
        ((b'a' + (d % 26) as u8) as char)
    }
}

public class Solution {
    public char KthCharacter(long k, int[] operations) {
        long n = 1;
        int i = 0;
        while (n < k) {
            n *= 2;
            ++i;
        }
        int d = 0;
        while (n > 1) {
            if (k > n / 2) {
                k -= n / 2;
                d += operations[i - 1];
            }
            n /= 2;
            --i;
        }
        return (char)('a' + (d % 26));
    }
}

class Solution {
    /**
     * @param Integer $k
     * @param Integer[] $operations
     * @return String
     */
    function kthCharacter($k, $operations) {
        $n = 1;
        $i = 0;
        while ($n < $k) {
            $n *= 2;
            ++$i;
        }
        $d = 0;
        while ($n > 1) {
            if ($k > $n / 2) {
                $k -= $n / 2;
                $d += $operations[$i - 1];
            }
            $n /= 2;
            --$i;
        }
        return chr(ord('a') + ($d % 26));
    }
}

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

Description

Solutions

Solution 1: Recurrence

Comments