Replace All Digits with Characters - Solution & Explanation
Problem Statement
You are given a 0-indexed string s that has lowercase English letters in its even indices and digits in its odd indices.
You must perform an operation 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'andshift('x', 0) = 'x'.
For every odd index i, you want to replace the digit s[i] with the result of the shift(s[i-1], s[i]) operation.
Return s after replacing all digits. It is guaranteed that shift(s[i-1], s[i]) will never exceed 'z'.
Note that shift(c, x) is not a preloaded function, but an operation to be implemented as part of the solution.
Example 1:
Input: s = "a1c1e1"
Output: "abcdef"
Explanation: The digits are replaced as follows:
- s[1] -> shift('a',1) = 'b'
- s[3] -> shift('c',1) = 'd'
- s[5] -> shift('e',1) = 'f'
Example 2:
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:
1 <= s.length <= 100sconsists only of lowercase English letters and digits.shift(s[i-1], s[i]) <= 'z'for all odd indicesi.
Approach Overview
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.
Approach 1: Approach 1: Simple Iteration and Replacement
This approach involves iterating through the string and focusing on odd indices where digits are located. For each odd index, compute the shifted character by taking the preceding character and shifting it by the digit at the current index. Replace the digit with the shifted character.
This C code iterates through the string, checking each odd index which holds a digit. It shifts the previous even-indexed character by the digit and replaces the digit with the new character. The original string's memory is reused.
Complexity
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(1) since we modify the string in place.
Approach 2: Approach 2: Using StringBuilder/Mutable Structures
This approach makes use of mutable structures like StringBuilder in Java or similar to efficiently handle string modifications. This way, elements can be directly altered without back-and-forth conversion between structures.
This Java solution leverages the StringBuilder class, which allows for mutable string modification, resulting in more efficient string operations compared to string immutability overhead.
Complexity
Time Complexity: O(n) where n is the length of the input string.
Space Complexity: O(n) as we use a StringBuilder to handle changes.
Approach 3: Simulation
Traverse the string, for characters at odd indices, replace them with the character that is a certain number of positions after the previous character.
Finally, return the replaced string.
The time complexity is O(n), where n is the length of the string s. Ignoring the space consumption of the answer, the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Simple Iteration and Replacement | Time Complexity: O(n) where n is the length of the string. |
| Approach 2: Using StringBuilder/Mutable Structures | Time Complexity: O(n) where n is the length of the input string. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iteration and Replacement | O(n) | O(n) | General case. Clean and easy approach for most languages. |
| StringBuilder / Mutable Structure | O(n) | O(n) | Preferred in languages with immutable strings like Java or Python to avoid repeated allocations. |
Video Solution
1844 Replace All Digits with Characters (Leetcode) | Easy Solution • PNT Coding • 1,676 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Replace All Digits with Characters easy or hard?
Replace All Digits with Characters Python/Java solution
How to solve Replace All Digits with Characters in O(n)?
What is the best approach for Replace All Digits with Characters?
Is Replace All Digits with Characters asked at Google/Amazon/Meta?
What data structure is used in Replace All Digits with Characters?
What is the time complexity of Replace All Digits with Characters?
Ready to solve this problem?
Practice Replace All Digits with Characters with our built-in code editor and test cases.
Practice on FleetCode