Code Implementation

class Solution:
    def replaceDigits(self, s: str) -> str:
        res = []
        for i in range(len(s)):
            if i % 2 == 0:
                res.append(s[i])
            else:
                # s[i] is a digit, s[i-1] is a letter
                shift = int(s[i])
                res.append(chr(ord(s[i-1]) + shift))
        return ''.join(res)
      

class Solution {
public:
    string replaceDigits(string s) {
        for (int i = 1; i < s.size(); i += 2) {
            s[i] = s[i-1] + (s[i] - '0');
        }
        return s;
    }
};
      

class Solution {
    public String replaceDigits(String s) {
        char[] arr = s.toCharArray();
        for (int i = 1; i < arr.length; i += 2) {
            arr[i] = (char)(arr[i-1] + (arr[i] - '0'));
        }
        return new String(arr);
    }
}
      

var replaceDigits = function(s) {
    let arr = s.split('');
    for (let i = 1; i < arr.length; i += 2) {
        arr[i] = String.fromCharCode(arr[i-1].charCodeAt(0) + parseInt(arr[i]));
    }
    return arr.join('');
};
      

Problem Description

You are given a string s that consists of lowercase English letters and digits. The string has the following property: for every even index i, s[i] is a lowercase English letter, and for every odd index i, s[i] is a digit from '0' to '9'.

Your task is to replace every digit at an odd index i with a character that is the result of shifting the previous letter s[i-1] forward in the alphabet by the integer value of s[i]. For example, if s[i-1] = 'a' and s[i] = '2', then s[i] should be replaced with 'c'.

Return the resulting string after all replacements have been made.

• Each digit is replaced exactly once.
• You must not reuse or skip any element; process the string in order.
• There is only one valid solution for each input.

Thought Process

At first glance, the problem looks like it could involve a lot of string manipulation and edge cases. A brute-force approach might involve building a new string character by character, checking each index to see if it's a digit, and then replacing it accordingly.

However, the structure of the input makes things simpler: every even index is a letter, and every odd index is a digit that should be replaced by shifting the previous letter. This regular pattern means we can process the string in pairs: for each even index (the letter), and the following odd index (the digit), we can easily compute the replacement.

Instead of building a complicated solution, we can iterate through the string, and whenever we encounter a digit, we use the previous character and the digit to compute the shifted letter. This is more efficient and easier to implement.

Solution Approach

• Iterate through the string from the beginning to the end.
• For every index i:
  • If i is even (i.e., i % 2 == 0), append s[i] (the letter) to the result.
  • If i is odd, calculate the new character by:
    • Converting s[i-1] (previous letter) to its ASCII value.
    • Converting s[i] (digit) to an integer.
    • Adding the integer to the ASCII value of the letter.
    • Converting the sum back to a character.
    • Appending this new character to the result.
• After processing all characters, join the result list into a single string and return it.

This approach is efficient because:

• We only need a single pass through the string (O(n) time).
• We use simple arithmetic and character operations, which are fast and easy to understand.
• No extra data structures (like hash maps) are needed, since the transformation is local to each character pair.

Example Walkthrough

Let's consider the input s = "a1c1e1".

1. Start with an empty result.
2. Index 0: 'a' (even) → append 'a' to result.
3. Index 1: '1' (odd) → shift previous letter 'a' by 1 → 'b', append 'b'.
4. Index 2: 'c' (even) → append 'c'.
5. Index 3: '1' (odd) → shift previous letter 'c' by 1 → 'd', append 'd'.
6. Index 4: 'e' (even) → append 'e'.
7. Index 5: '1' (odd) → shift previous letter 'e' by 1 → 'f', append 'f'.
8. Join result: ['a', 'b', 'c', 'd', 'e', 'f'] → "abcdef".

At each odd index, we look at the previous character and the digit, and replace the digit with the shifted letter.

Time and Space Complexity

• Brute-force approach:
  • Would still be O(n) time and O(n) space, since we have to examine each character and build a new string.
  • No nested loops or extra data structures are required.
• Optimized approach (as above):
  • Time Complexity: O(n), where n is the length of s. Each character is processed exactly once.
  • Space Complexity: O(n), for storing the result string.
• The main improvement is in simplicity and clarity, not asymptotic complexity, since the problem is inherently linear.

Summary

The "Replace All Digits with Characters" problem leverages the regular structure of the input string: alternating letters and digits. By iterating through the string and using simple arithmetic to shift letters by digit values, we can efficiently build the resulting string in a single pass. The key insight is recognizing that each digit only depends on its immediately preceding letter, allowing for a straightforward and elegant solution with linear time and space complexity.