3304. Find the K-th Character in String Game I

Description

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

You are given a positive integer k.

Now Bob will ask Alice to perform the following operation forever:

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 enough operations have been done for word to have at least k characters.

Example 1:

Input: k = 5

Output: "b"

Explanation:

Initially, word = "a". We need to do the operation three times:

Generated string is "b", word becomes "ab".
Generated string is "bc", word becomes "abbc".
Generated string is "bccd", word becomes "abbcbccd".

Example 2:

Input: k = 10

Output: "c"

Constraints:

1 <= k <= 500

Solutions

Solution 1: Simulation

Thinking

Each operation appends a copy of the current word with every letter shifted by one, doubling the length. Since \(k \le 500\), we can simulate until the length is at least \(k\).

Storing offsets in \(0..25\) avoids building strings: the appended half is the old half plus one, modulo \(26\).

The answer is the letter at index \(k-1\) once the array is long enough.

We can use an array \(\textit{word}\) to store the string after each operation. When the length of \(\textit{word}\) is less than \(k\), we continuously perform operations on \(\textit{word}\).

Finally, return \(\textit{word}[k - 1]\).

The time complexity is \(O(k)\), and the space complexity is \(O(k)\). Here, \(k\) is the input parameter.

Python3JavaC++GoTypeScriptRust

class Solution:
    def kthCharacter(self, k: int) -> str:
        word = [0]
        while len(word) < k:
            word.extend([(x + 1) % 26 for x in word])
        return chr(ord("a") + word[k - 1])

class Solution {
    public char kthCharacter(int k) {
        List<Integer> word = new ArrayList<>();
        word.add(0);
        while (word.size() < k) {
            for (int i = 0, m = word.size(); i < m; ++i) {
                word.add((word.get(i) + 1) % 26);
            }
        }
        return (char) ('a' + word.get(k - 1));
    }
}

class Solution {
public:
    char kthCharacter(int k) {
        vector<int> word;
        word.push_back(0);
        while (word.size() < k) {
            int m = word.size();
            for (int i = 0; i < m; ++i) {
                word.push_back((word[i] + 1) % 26);
            }
        }
        return 'a' + word[k - 1];
    }
};

func kthCharacter(k int) byte {
    word := []int{0}
    for len(word) < k {
        m := len(word)
        for i := 0; i < m; i++ {
            word = append(word, (word[i]+1)%26)
        }
    }
    return 'a' + byte(word[k-1])
}

function kthCharacter(k: number): string {
    const word: number[] = [0];
    while (word.length < k) {
        word.push(...word.map(x => (x + 1) % 26));
    }
    return String.fromCharCode(97 + word[k - 1]);
}

impl Solution {
    pub fn kth_character(k: i32) -> char {
        let mut word = vec![0];
        while word.len() < k as usize {
            let m = word.len();
            for i in 0..m {
                word.push((word[i] + 1) % 26);
            }
        }
        (b'a' + word[(k - 1) as usize] as u8) as char
    }
}

3304. Find the K-th Character in String Game I

Description

Solutions

Solution 1: Simulation

Comments