Replace All Digits with Characters solution and explanation
Google
9 more videos on this problem
1844 Replace All Digits with Characters (Leetcode) | Easy SolutionPNT Coding · 11:33 · 1K views
1844. Replace All Digits with Characters (Leetcode Easy)Programming Live with Larry · 3:08 · 727 views
LeetCode 1844 | Replace All Digits with Characters | StringBuilder | JavaSleepy Cracker · 3:48 · 575 views
LeetCode [easy] Replace All Digits with CharactersFrancesco Manicardi · 2:02 · 503 views
Leetcode 1844. Replace All Digits with CharactersMath Geeks · 3:15 · 324 views
Leetcode #1844 Replace All Digits with Characters | C++ Solution ExplainedJoshProgramin · 10:55 · 253 views
Replace All Digits with Characters - TypeScriptSinno Tech · 11:34 · 71 views
LeetCode 1844 Python Solution | Replace All Digits with Characters Explained | Easy Problem TutorialCoding with Seattle Brandon · 2:40 · 45 views
LeetCode 1844: Replace All Digits with CharactersAlitaCode · 26:58 · 11 views
1844. Replace All Digits with Characters | LeetCode Problem Solving Playlist | Easy SolutionHet Roy · 6:23 · 10 views
The problem
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.
def replace_digits(s):
s = list(s)
for i in range(1, len(s), 2):
s[i] = chr(ord(s[i - 1]) + int(s[i]))
return ''.join(s)
print(replace_digits("a1c1e1"))public class Solution {
public static 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);
}
public static void main(String[] args) {
System.out.println(replaceDigits("a1c1e1"));
}
}#include <iostream>
#include <string>
std::string replaceDigits(std::string s) {
for (int i = 1; i < s.size(); i += 2) {
s[i] = s[i-1] + (s[i] - '0');
}
return s;
}
int main() {
std::string s = "a1c1e1";
std::cout << replaceDigits(s) << std::endl;
return 0;
}function replaceDigits(s) {
let arr = s.split('');
for (let i = 1; i < arr.length; i += 2) {
arr[i] = String.fromCharCode(arr[i - 1].charCodeAt(0) + Number(arr[i]));
}
return arr.join('');
}
console.log(replaceDigits("a1c1e1"));#include <stdio.h>
#include <stdlib.h>
char* replaceDigits(char* s) {
int i;
for (i = 1; s[i] != '\0'; i += 2) {
s[i] = s[i-1] + (s[i] - '0');
}
return s;
}
int main() {
char s[] = "a1c1e1";
printf("%s\n", replaceDigits(s));
return 0;
}using System;
class Solution {
public static 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);
}
static void Main(string[] args) {
Console.WriteLine(ReplaceDigits("a1c1e1"));
}
}In this Python solution, the string is converted to a list of characters, then iterated through with replacements of odd-index digits after computation using character shifts. The list is then joined back into a string.
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(n) since a list of characters is created.
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.
def replace_digits(s):
s = list(s)
# Python does not have StringBuilder, but lists can be used similarly for mutable strings
for i in range(1, len(s), 2):
s[i] = chr(ord(s[i - 1]) + int(s[i]))
return ''.join(s)
print(replace_digits("a1c1e1"))import java.lang.StringBuilder;
public class Solution {
public static String replaceDigits(String s) {
StringBuilder sb = new StringBuilder(s);
for (int i = 1; i < sb.length(); i += 2) {
sb.setCharAt(i, (char)(sb.charAt(i - 1) + (sb.charAt(i) - '0')));
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(replaceDigits("a1c1e1"));
}
}While Python does not have a direct equivalent to StringBuilder, lists are utilized similarly to efficiently manage and modify string content by index, leveraging inbuilt functions to join elements back into string form.
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(n) due to construction and manipulation of character list.
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).
function replaceDigits(s: string): string {
const n = s.length;
const ans = [...s];
for (let i = 1; i < n; i += 2) {
ans[i] = String.fromCharCode(ans[i - 1].charCodeAt(0) + Number(ans[i]));
}
return ans.join('');
}func replaceDigits(s string) string {
cs := []byte(s)
for i := 1; i < len(s); i += 2 {
cs[i] = cs[i-1] + cs[i] - '0'
}
return string(cs)
}impl Solution {
pub fn replace_digits(s: String) -> String {
let n = s.len();
let mut ans = s.into_bytes();
let mut i = 1;
while i < n {
ans[i] = ans[i - 1] + (ans[i] - b'0');
i += 2;
}
ans.into_iter().map(char::from).collect()
}
}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 string. |
| Simulation | – |
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. |
Frequently asked questions
Is Replace All Digits with Characters easy or hard?
Replace All Digits with Characters is classified as an Easy problem. The task focuses on basic string traversal and character arithmetic rather than complex data structures or algorithms.
Replace All Digits with Characters Python/Java solution
In Python, iterate through the string and append characters to a list, converting digits using chr(ord(previous) + digit). In Java, use a StringBuilder and compute the shifted character with (char)(previous + digit). Both implementations run in O(n) time and O(n) space.
How to solve Replace All Digits with Characters in O(n)?
Iterate through the string while building a result string. When a letter appears, append it directly. When a digit appears, convert it to an integer and add it to the ASCII value of the previous character to compute the shifted letter. Append that computed character and continue scanning until the end.
What is the best approach for Replace All Digits with Characters?
A single-pass iteration over the string is the best approach. For each digit, shift the previous character forward in the alphabet using ASCII arithmetic and append the result. This method runs in O(n) time with O(n) space and is the standard solution used in most editorials.
Is Replace All Digits with Characters asked at Google/Amazon/Meta?
This problem is categorized as an easy string manipulation question and appears in practice sets similar to those used in technical screens. Large companies like Google, Amazon, and Meta often include variations of string processing problems that test iteration, ASCII operations, and careful indexing.
What data structure is used in Replace All Digits with Characters?
The solution mainly relies on string traversal and optional mutable string structures. Implementations often use a StringBuilder in Java, a character list in Python, or direct string building in languages where concatenation is efficient.
What is the time complexity of Replace All Digits with Characters?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed exactly once, and the shift calculation is constant time. Space complexity is O(n) because a new string or builder is created to store the result.