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

EasyBit ManipulationRecursionMathSimulation

Problem Description

Alice and Bob are engaged in a game where Alice begins with a string word = "a". The game involves a positive integer k, and Bob will ask Alice to perform an operation repeatedly: for each character in word, change it to its next character in the English alphabet and append this new sequence to the original word. For example, transforming "c" becomes "cd", and transforming "zb" becomes "zbac". You need to determine the value of the k-th character in word after it becomes sufficiently long to include k characters. Note that after 'z', the character cycles back to 'a'.

Intuition

To solve the problem, the approach is to simulate the process described. Start with word = [0] representing the initial string "a". Iteratively transform each character in word by adding 1 to its numeric representation (modulo 26 to handle wrap-around from 'z' to 'a'), and extend the list with these new values. Continue this process until word has at least k elements. At that point, the k-th character corresponds to the numeric value at position k - 1 in the word array. Convert this numeric value back to a character starting from 'a' to get the desired result.

Learn more about Recursion and Math patterns.

Solution Approach

To implement the solution, we use an array to simulate the transformation process of the string word. Here's a step-by-step breakdown of the method:

Initialize the Starting Point:
- Create a list word = [0], representing the initial string "a" as numeric values with 0 corresponding to 'a'.
Simulate the Transformation:
- While the length of word is less than k, extend word by adding the next character values. This is achieved using the list comprehension [(x + 1) % 26 for x in word].
- The operation (x + 1) % 26 ensures that after 'z', the next character is 'a'.
Extend the List:
- Append the results of the transformation to word, growing its length until it reaches or exceeds k.
Retrieve the k-th Character:
- Once word has at least k elements, find the character at the k-th position by using chr(ord("a") + word[k - 1]).
- Convert the numeric value in word back to a character using ASCII calculations, where ord("a") represents the starting point for alphabet characters.

This method efficiently simulates the successive transformations and directly fetches the desired k-th character once the expansion is complete.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example with k = 5 to demonstrate the solution approach.

Step 1: Initialize the Starting Point

Start with word = [0], which corresponds to the string "a".

Step 2: Simulate the Transformation

Since len(word) < 5, perform the transformation.
- Current word: [0] (represents "a").
- Transform using [(x + 1) % 26 for x in word]:
  - (0 + 1) % 26 = 1, which corresponds to "b".
- Extend word: [0, 1] (represents "ab").

Step 3: Continue Simulation

Again, since len(word) < 5, perform another transformation:
- Current word: [0, 1] (represents "ab").
- Transform each character:
  - (0 + 1) % 26 = 1 -> "b"
  - (1 + 1) % 26 = 2 -> "c"
- Extend word: [0, 1, 1, 2] (represents "abbc").
Continue transforming as len(word) < 5:
- Current word: [0, 1, 1, 2] (represents "abbc").
- Transform each character:
  - (0 + 1) % 26 = 1 -> "b"
  - (1 + 1) % 26 = 2 -> "c"
  - (1 + 1) % 26 = 2 -> "c"
  - (2 + 1) % 26 = 3 -> "d"
- Extend word: [0, 1, 1, 2, 1, 2, 2, 3] (represents "abbcbccd").

Step 4: Retrieve the k-th Character

Now len(word) ≥ 5. The 5th character value in word is 1.
Convert this numeric value to a character:
- chr(ord("a") + 1) = 'b'.

Thus, the 5th character in the resulting sequence is 'b'.

Solution Implementation

1class Solution:
2    def kthCharacter(self, k: int) -> str:
3        # Start the sequence with the first character index '0' representing 'a'
4        word = [0]
5
6        # Continue extending the sequence until its length is at least `k`
7        while len(word) < k:
8            # Extend the current word by appending characters one step forward in the alphabet
9            # Using modulo 26 to wrap around after 'z' back to 'a'
10            word.extend([(x + 1) % 26 for x in word])
11      
12        # Convert the k-th character index to its corresponding character
13        # `ord("a") + word[k - 1]` calculates the ASCII value of the character
14        # `chr()` converts the ASCII value back to a character
15        return chr(ord("a") + word[k - 1])
16

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public char kthCharacter(int k) {
6        // Initialize a list to store encodings of characters. 
7        // Start with encoding for 'a', which is 0.
8        List<Integer> word = new ArrayList<>();
9        word.add(0);
10      
11        // Continue adding characters to the list until we reach the k-th character.
12        while (word.size() < k) {
13            int currentSize = word.size(); // Store current size of 'word' list.
14          
15            // Iterate over the current list to determine the next sequence of characters.
16            for (int i = 0; i < currentSize; ++i) {
17                // Add the next character in sequence, wrapping around using modulo 26
18                // to ensure it stays within the range 'a' to 'z'.
19                word.add((word.get(i) + 1) % 26);
20            }
21        }
22      
23        // Convert the k-th character from its integer encoding to a character
24        // by adding 'a' to it and cast to 'char'.
25        return (char) ('a' + word.get(k - 1));
26    }
27}
28

1#include <vector>  // Include the vector library
2
3class Solution {
4public:
5    // Method to find the k-th character in the sequence
6    char kthCharacter(int k) {
7        std::vector<int> word;  // Initialize a vector to store the sequence
8        word.push_back(0);      // Start with the first character represented by 0
9      
10        // Continue generating the sequence until it reaches at least k elements
11        while (word.size() < k) {
12            int currentSize = word.size();  // Current size of the vector
13            // Double the sequence by adding 1 modulo 26 to each element
14            for (int i = 0; i < currentSize; ++i) {
15                word.push_back((word[i] + 1) % 26);
16            }
17        }
18      
19        // Return the k-th character, adjust for zero-based indexing
20        return 'a' + word[k - 1];
21    }
22};
23

1// Function to find the k-th character in a sequence derived from incremental patterns
2function kthCharacter(k: number): string {
3    // Initialize the sequence with the starting character represented as a number
4    const word: number[] = [0];
5
6    // Build the sequence until it is long enough to access the k-th character
7    while (word.length < k) {
8        // For every element in the current sequence, map it to the next character in a cyclic alphabet order
9        word.push(...word.map(x => (x + 1) % 26));
10    }
11
12    // Convert the k-th number to its corresponding lowercase alphabet character
13    return String.fromCharCode(97 + word[k - 1]);
14}
15

Time and Space Complexity

The provided code has a time complexity of O(k) because the while loop continues until the length of the word list reaches k. Inside the loop, it extends the list by iterating over its current elements, which takes linear time relative to the size of the list.

The space complexity is also O(k) because the list word expands until it contains k elements, requiring space proportional to k.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

BFS

DFS

Both

Neither

I don’t know