1844. Replace All Digits with Characters

EasyString

Problem Description

In this problem, we are given a string where lowercase English letters are placed at even indices (0, 2, 4, ...), and digits at odd indices (1, 3, 5, ...). We need to transform this string by using a special shift function. The shift function takes a character c and a digit x, and returns the character which is x positions after c in the alphabet sequence.

The task is to replace every digit in the string at an odd index i with the character obtained by shifting the preceding letter (at index i-1) by the digit at i. The process will transform the string into a new version with no digits, and only letters. Additionally, we are assured that applying the shift operation will not produce a character beyond 'z'.

For example, if we have s = "a1b2", after replacement, the resulting string should be s = "abbc", because 'a' shifted by 1 position gives 'b', and 'b' shifted by 2 positions gives 'c'.

Intuition

To solve this problem, we can iterate over the string and perform the shift operation on every odd index. We know that the indices of the string start at 0, and we can access each character of the string using these indices. The key idea is to convert each digit at an odd index i into the corresponding shift character by using the previous character at index i-1. We repeat this procedure for all the odd indices in the string.

For the actual shift operation, we leverage the ASCII values of characters. The ASCII value of a letter can be obtained with Python's ord() function, and we can add the digit directly to this value because the digit at odd indices is already a number. We must convert the digit from string to integer before adding. After shifting, we can get the character back from its ASCII value using the chr() function. We replace the digit with this new character in the string.

To facilitate these operations, we convert the string s into a list because strings in Python are immutable, while lists are mutable. After iterating through the string and applying the shift operation to all digits, we join the list to form the final transformed string with no digits left.

Solution Approach

The core of our approach is based on the idea that we need to modify only the digits in the original string, and each digit needs to be offset by its own value from the preceding character. The flow of the solution is as follows:

Convert the string s into a list to allow for modification, since Python strings are immutable and don't allow changes to individual characters directly.
Iterate over the list starting from the first odd index (which is 1) to the end of the list, and increment by 2 each time to only visit the odd indices where the digits are located.
Retrieve the character that comes before the current digit (s[i - 1]) and find its ASCII value using ord(). ASCII values are numeric representations of characters that can be manipulated mathematically.
Convert the current digit (s[i]) from a string to an integer so that it can be used in the arithmetic operation.
Calculate the ASCII value of the new character by adding the integer value of the digit to the ASCII value of the preceding character.
Convert the new ASCII value back into a character using chr().
Replace the digit in the list with the new character.
After the iteration, join the elements of the list together into a string using ''.join(s).

In this solution:

A for loop is employed to iterate over the string indices. The range starts at 1 (the first odd index) and goes up to len(s), which is the length of the string, with steps of 2 to ensure we're only looking at the odd indices.
Python's built-in ord function is used to get the ASCII value of a character. It converts the given string of length 1 to an integer representing the Unicode code point of the character. For example, ord('a') returns 97 which is the Unicode point for the character 'a'.
Python's built-in chr function is used to convert the adjusted ASCII value back into a character. This function returns a string representing a character whose Unicode code point is the integer. For example, chr(98) returns 'b'.
An implicit data structure, a list, is used to allow mutation of the string.

Here is a step-by-step description of the algorithm applied within the for loop for the digit at odd index i:

1. ASCII_preceding_char = ord(s[i - 1])
2. offset = int(s[i])
3. ASCII_new_char = ASCII_preceding_char + offset
4. new_char = chr(ASCII_new_char)
5. s[i] = new_char

These steps are repeated until every digit at an odd index in the given string is replaced with a corresponding character as per the shift function. This is the essence of the solution, and the output is the modified string.

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 consider a small example using the string s = "a5c3" to illustrate the solution approach described above.

First, we convert the string s into a list to allow modifications. The string as a list will be ['a', '5', 'c', '3'].
We will then start iterating over the list from the first odd index, which is 1. This index points to the digit '5'.

According to the steps in the solution approach, we first find the ASCII value of the preceding character 'a' (which is at index 0):

ASCII_preceding_char = ord('a') // ASCII_preceding_char = 97

We then convert the current digit '5' into an integer and add it to the ASCII value of the preceding character:

offset = int('5') // offset = 5
ASCII_new_char = ASCII_preceding_char + offset // ASCII_new_char = 97 + 5 = 102

Next, we convert the ASCII value back into a character:

new_char = chr(ASCII_new_char) // new_char = chr(102) = 'f'

Replace the digit with the new character in our list:

['a', '5', 'c', '3'] becomes ['a', 'f', 'c', '3']

We move to the next odd index, which is 3. Repeat the steps:

ASCII_preceding_char = ord('c') // ASCII_preceding_char = 99
offset = int('3') // offset = 3
ASCII_new_char = ASCII_preceding_char + offset // ASCII_new_char = 99 + 3 = 102
new_char = chr(ASCII_new_char) // new_char = chr(102) = 'f'

We replace the digit at index 3 with the new character in our list:

['a', 'f', 'c', '3'] becomes ['a', 'f', 'c', 'f']

After completing the iteration for all odd indices, we join the elements of the list into a string:

''.join(['a', 'f', 'c', 'f']) // The final transformed string is "afcf"

And there we have it! The original string s = "a5c3" has been successfully transformed into s = "afcf" following the provided solution approach, correctly applying the shift operation to the digits.

Solution Implementation

1class Solution:
2    def replaceDigits(self, s: str) -> str:
3        # Convert the string to a list of characters for easy manipulation
4        char_list = list(s)
5      
6        # Iterate over the character list, jumping in steps of 2 (starting from index 1)
7        for i in range(1, len(char_list), 2):
8            # Replace the digit at the odd index with a char that is `digit` away from the char at the even index
9            # before it, using ASCII values.
10            char_list[i] = chr(ord(char_list[i - 1]) + int(char_list[i]))
11          
12        # Join the list of characters back into a string and return
13        return ''.join(char_list)
14

1class Solution {
2    // This method replaces all digits in the string with a character shifted by the digit value.
3    public String replaceDigits(String s) {
4        // Convert the input string into a character array for easy manipulation.
5        char[] charArray = s.toCharArray();
6      
7        // Loop through the character array starting from index 1, incrementing by 2,
8        // to process only the digit characters.
9        for (int i = 1; i < charArray.length; i += 2) {
10            // Shift the character before the digit ('0' through '9') by the digit value. 
11            // The digit character is converted to the actual digit by subtracting '0'.
12            // Then add this numerical value to the preceding character to shift it.
13            charArray[i] = (char) (charArray[i - 1] + (charArray[i] - '0'));
14        }
15      
16        // Convert the altered character array back to a string and return it.
17        return String.valueOf(charArray);
18    }
19}
20

1class Solution {
2public:
3    // Function to replace digits in a string with characters shifted accordingly
4    string replaceDigits(string s) {
5        // Determine the size of the string to iterate through it
6        int strSize = s.size();
7      
8        // Loop through the string, incrementing by 2 to only handle the digits
9        for (int i = 1; i < strSize; i += 2) {
10            // Replace each digit at an odd index with the character that is
11            // shifted by the digit's value from the previous character.
12            // The expression s[i] - '0' converts the digit character to its
13            // integer value, and we add this value to the previous character.
14            s[i] = s[i - 1] + (s[i] - '0');
15        }
16      
17        // Return the modified string
18        return s;
19    }
20};
21

1function replaceDigits(s: string): string {
2    // Get the length of the input string
3    const stringLength = s.length;
4
5    // Split the input string into an array to manipulate individual characters
6    const answerArray = [...s];
7
8    // Iterate over the characters of the string, skipping every other character
9    for (let index = 1; index < stringLength; index += 2) {
10        // Replace the current character (digit) with the character that is 'digit' positions
11        // after the letter that precedes it in the alphabet.
12        // 'charCodeAt(0)' gets the ASCII code of the letter at 'index - 1',
13        // 'Number(answerArray[index])' converts the character at 'index' into a number,
14        // and 'String.fromCharCode' converts the new ASCII code back to a character.
15        answerArray[index] = String.fromCharCode(answerArray[index - 1].charCodeAt(0) + Number(answerArray[index]));
16    }
17
18    // Join the array of characters back into a string and return it
19    return answerArray.join('');
20}
21

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the length of the string s. This is because the for loop iterates over every other element of the string, performing a constant-time operation for half the characters (the digits). Each operation inside the loop (calculating ord, adding an integer, converting back to a character with chr, and assigning it back to the list) takes constant time. Therefore, the time taken is directly proportional to the number of characters in the string.

Space Complexity

The space complexity of the code is O(n), as the input string s is converted to a list, which takes up space proportional to the length of s. No additional data structures are used that grow with the input size, and the space used for the output is the same as the space used to store the modified list created from the input string.

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

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

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know