Replace All Digits with Characters

Difficulty: Easy | Acceptance: 82.70% | Paid: No Topics: String

You are given a 0-indexed string s that has lowercase English letters in its even indices and digits in its odd indices.

There is a function shift(c, x), where c is a character and x is a digit, that returns the xth character after c.

For example, shift(‘a’, 5) = ‘f’ and shift(‘x’, 0) = ‘x’.

For every odd index i, you want to replace the digit at s[i] with shift(s[i-1], s[i]).

Return s after replacing all digits. It is guaranteed that all shift operations have valid results.

• Examples
• Constraints
• Iterative String Building
• In-place Character Array Modification
• Recursive Solution

Examples

Input: s = "a1c1e"
Output: "abcde"
Explanation: The digits are replaced as follows:
- s[1] = shift('a',1) = 'b'
- s[3] = shift('c',1) = 'd'

Input: s = "a1b2c3d4e"
Output: "abbdcfdhe"
Explanation: The digits are replaced as follows:
- s[1] = shift('a',1) = 'b'
- s[3] = shift('b',2) = 'd'
- s[5] = shift('c',3) = 'f'
- s[7] = shift('d',4) = 'h'

Constraints

2 <= s.length <= 100
s consists only of lowercase English letters and digits.
s is guaranteed to have an even number of digits.
All shift operations have valid results.

Iterative String Building

Intuition Iterate through the string character by character, keeping letters as-is and converting digits to shifted characters based on the previous letter.

Steps

• Initialize an empty result list/array
• Loop through each character with its index
• If index is even, append the character directly
• If index is odd, calculate shifted character using ASCII values and append
• Join the result list into a string and return

class Solution:
    def replaceDigits(self, s: str) -> str:
        result = []
        for i, ch in enumerate(s):
            if i % 2 == 0:
                result.append(ch)
            else:
                prev = s[i - 1]
                shift = int(ch)
                result.append(chr(ord(prev) + shift))
        return ''.join(result)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the result string
• Notes: Uses StringBuilder in Java for efficient concatenation

In-place Character Array Modification

Intuition Convert the string to a mutable character array and modify digits in-place by iterating through odd indices only.

Steps

• Convert string to character array
• Iterate through odd indices (1, 3, 5, …)
• For each odd index, calculate shifted character from previous character
• Replace the digit with the shifted character
• Convert back to string and return

class Solution:
    def replaceDigits(self, s: str) -> str:
        chars = list(s)
        for i in range(1, len(chars), 2):
            prev = chars[i - 1]
            shift = int(chars[i])
            chars[i] = chr(ord(prev) + shift)
        return ''.join(chars)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the character array (O(1) in C++ since strings are mutable)
• Notes: More memory efficient as we only iterate through odd indices

Recursive Solution

Intuition Use recursion to process the string, handling each character and building the result by combining the current character with the result of processing the rest.

Steps

• Define a recursive helper function with index parameter
• Base case: if index exceeds string length, return empty string
• If index is even, return current character plus recursive result
• If index is odd, calculate shifted character and return it plus recursive result
• Start recursion from index 0

class Solution:
    def replaceDigits(self, s: str) -> str:
        def helper(i):
            if i >= len(s):
                return ''
            if i % 2 == 0:
                return s[i] + helper(i + 1)
            else:
                prev = s[i - 1]
                shift = int(s[i])
                return chr(ord(prev) + shift) + helper(i + 1)
        return helper(0)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for recursion stack and result string
• Notes: Not recommended for production due to stack overflow risk on large inputs