Replace All Digits with Characters - Video Solutions

Problem Overview: The string contains lowercase letters at even indices and digits at odd indices. Each digit represents how many positions to shift the previous character forward in the alphabet. Replace every digit with the resulting shifted character and return the final string.

Approach 1: Simple Iteration and Replacement (Time: O(n), Space: O(n))

Traverse the string from left to right and build a new result string. When you encounter a letter, append it directly. When you encounter a digit, convert it to an integer and shift the previous character forward by that amount using ASCII arithmetic. For example, if the previous character is 'a' and the digit is 2, the replacement becomes 'c'. This approach works because the problem guarantees the pattern of letter followed by digit. The algorithm performs a single pass over the string and only constant work per character.

The key operation is calculating the shifted character using chr(ord(previous) + digit) or equivalent in other languages. Since every character is processed once, the time complexity is O(n). The result string stores all characters, giving O(n) extra space. This method fits naturally with basic string manipulation and straightforward simulation logic.

Approach 2: Using StringBuilder / Mutable Structures (Time: O(n), Space: O(n))

Languages like Java and Python handle repeated string concatenation less efficiently due to immutability. Instead, use a mutable structure such as StringBuilder in Java or a list of characters in Python. Iterate through the input string and append characters to the builder. When a digit appears, compute the shifted character from the previous letter already stored in the builder and append it.

This method avoids repeated memory allocations that occur with naive string concatenation. The algorithm still performs a single pass over the input, so the time complexity remains O(n). Space usage stays O(n) because the builder holds the final transformed string. The difference is mostly implementation efficiency and cleaner code in languages with immutable strings.

Recommended for interviews: The simple iteration approach is exactly what interviewers expect. It demonstrates comfort with character arithmetic and linear string traversal. Implementing it with a mutable builder structure shows awareness of language-level performance details, which is a small but meaningful improvement in production-quality code.