Problem

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 ith 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 kth character in word after performing all the operations.

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

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8

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 <= 1014
  • 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.

Solution

Method 1 – Reverse Simulation and Length Tracking

Intuition

Instead of building the string (which is infeasible for large k), we track the length of the string after each operation. We then work backwards, simulating the operations in reverse to find the k-th character, reducing k as we go.

Approach

  1. Start with the initial string length (1 for “a”).
  2. For each operation, compute the new length:
    • If op is 0: double the length.
    • If op is 1: double the length (since we append a shifted version).
  3. Store all intermediate lengths.
  4. Work backwards from the last operation:
    • If op is 0: If k is in the second half, subtract the first half’s length.
    • If op is 1: If k is in the second half, subtract the first half’s length and increment a “shift” counter.
  5. When you reach the initial string, apply the total shift to ‘a’ to get the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    char kthCharacter(long long k, const std::vector<int>& ops) {
        char ch = 'a';
        std::vector<long long> v;
        v.push_back(1);
        for (int op : ops) {
            long long temp = 2 * v.back();
            v.push_back(temp > k ? k : temp);
        }
        for (int i = (int)ops.size() - 1; i >= 0; --i) {
            if (k > v[i]) {
                k -= v[i];
                if (ops[i] == 1) {
                    ch = (ch == 'z' ? 'a' : ch + 1);
                }
            }
        }
        return ch;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func KthCharacter(k int64, operations []int) byte {
    ch := byte('a')
    lens := []int64{1}
    for _, op := range operations {
        temp := 2 * lens[len(lens)-1]
        if temp > k {
            lens = append(lens, k)
        } else {
            lens = append(lens, temp)
        }
    }
    for i := len(operations) - 1; i >= 0; i-- {
        if k > lens[i] {
            k -= lens[i]
            if operations[i] == 1 {
                if ch == 'z' {
                    ch = 'a'
                } else {
                    ch++
                }
            }
        }
    }
    return ch
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public char kthCharacter(long k, int[] operations) {
        char ch = 'a';
        long[] lens = new long[operations.length + 1];
        lens[0] = 1;
        for (int i = 0; i < operations.length; i++) {
            long temp = 2 * lens[i];
            lens[i+1] = temp > k ? k : temp;
        }
        for (int i = operations.length - 1; i >= 0; i--) {
            if (k > lens[i]) {
                k -= lens[i];
                if (operations[i] == 1) {
                    ch = (ch == 'z') ? 'a' : (char)(ch + 1);
                }
            }
        }
        return ch;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun kthCharacter(k: Long, operations: IntArray): Char {
        var ch = 'a'
        val lens = LongArray(operations.size + 1)
        lens[0] = 1
        for (i in operations.indices) {
            val temp = 2 * lens[i]
            lens[i+1] = if (temp > k) k else temp
        }
        var kk = k
        for (i in operations.size - 1 downTo 0) {
            if (kk > lens[i]) {
                kk -= lens[i]
                if (operations[i] == 1) {
                    ch = if (ch == 'z') 'a' else ch + 1
                }
            }
        }
        return ch
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def kthCharacter(self, k: int, operations: list[int]) -> str:
        ch = 'a'
        lens = [1]
        for op in operations:
            temp = 2 * lens[-1]
            lens.append(k if temp > k else temp)
        for i in range(len(operations) - 1, -1, -1):
            if k > lens[i]:
                k -= lens[i]
                if operations[i] == 1:
                    ch = chr((ord(ch) - ord('a') + 1) % 26 + ord('a'))
        return ch
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn kth_character(k: i64, operations: Vec<i32>) -> char {
        let mut ch = b'a';
        let mut lens = vec![1i64];
        for &op in &operations {
            let temp = 2 * lens[lens.len() - 1];
            lens.push(if temp > k { k } else { temp });
        }
        let mut kk = k;
        for i in (0..operations.len()).rev() {
            if kk > lens[i] {
                kk -= lens[i];
                if operations[i] == 1 {
                    ch = if ch == b'z' { b'a' } else { ch + 1 };
                }
            }
        }
        ch as char
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    kthCharacter(k: number, operations: number[]): string {
        let ch = 'a'.charCodeAt(0);
        const lens = [1];
        for (const op of operations) {
            const temp = 2 * lens[lens.length - 1];
            lens.push(temp > k ? k : temp);
        }
        for (let i = operations.length - 1; i >= 0; i--) {
            if (k > lens[i]) {
                k -= lens[i];
                if (operations[i] === 1) {
                    ch = ch === 'z'.charCodeAt(0) ? 'a'.charCodeAt(0) : ch + 1;
                }
            }
        }
        return String.fromCharCode(ch);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of operations, since we process each operation twice (once forward, once backward).
  • 🧺 Space complexity: O(n), for storing the lengths of the string after each operation.