Replace All Digits with Characters
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves building the output string by repeatedly concatenating characters in a loop. For each character in the input string, it decides whether to append the character as is (for letters at even indices) or to compute and append the shifted character (for digits at odd indices). While straightforward, this method is very inefficient in Java.
Algorithm
- Initialize an empty string, let's call it
result. - Iterate through the input string
sfrom the first character to the last, using an indexi. - If the current index
iis even, it meanss.charAt(i)is a letter. Append this character directly to theresultstring. - If the current index
iis odd, it meanss.charAt(i)is a digit. Perform the following:- Get the preceding character,
prevChar = s.charAt(i - 1). - Convert the digit character to its integer value:
shift = s.charAt(i) - '0'. - Calculate the new character:
newChar = (char)(prevChar + shift). - Append
newCharto theresultstring.
- Get the preceding character,
- After the loop finishes, return the
resultstring.
Walkthrough
The core idea is to iterate through the input string s and construct a new string. In Java, strings are immutable, so every time the + or += operator is used for concatenation, a new string object is created in memory. This involves copying all the characters from the old string to the new one, along with the new character being appended. This repeated copying is what leads to the quadratic time complexity.
For example, building a string of length N character by character will involve operations of cost O(1), O(2), ..., O(N-1), summing up to O(N^2).
Here is the implementation:
class Solution { public String replaceDigits(String s) { String result = ""; for (int i = 0; i < s.length(); i++) { if (i % 2 == 0) { result += s.charAt(i); } else { char prevChar = s.charAt(i - 1); int shift = s.charAt(i) - '0'; result += (char) (prevChar + shift); } } return result; }}Complexity
Time
O(N^2), where N is the length of the string. String concatenation inside a loop in Java takes time proportional to the length of the strings being joined. This results in a quadratic time complexity.
Space
O(N^2) in many Java versions. While the final string occupies O(N) space, the intermediate strings created during concatenation can lead to a total space allocation of O(N^2) over the course of the loop.
Trade-offs
Pros
The logic is very simple and easy to write and understand.
Cons
Extremely inefficient for all but the shortest strings due to O(N^2) time complexity.
Creates a large number of temporary
StringandStringBuilderobjects, leading to high memory churn and frequent garbage collection.
A much more efficient way to handle string modifications in a loop is to use the StringBuilder class. StringBuilder provides a mutable sequence of characters, allowing for efficient modifications like replacement, appending, or insertion without creating a new object for each change. This approach modifies a StringBuilder representation of the string in-place.
Algorithm
- Create a
StringBuilderinstance, initializing it with the input strings. - Iterate through the string using a loop that only visits the odd indices. The loop should start at
i = 1and increment by 2 in each step (i += 2). - Inside the loop, for each odd index
i:- Get the preceding character:
char prevChar = sb.charAt(i - 1). - Get the digit's integer value:
int shift = sb.charAt(i) - '0'. - Calculate the new character:
char newChar = (char)(prevChar + shift). - Use the
setCharAt(i, newChar)method of theStringBuilderto replace the digit at indexiwith the new character.
- Get the preceding character:
- After the loop, convert the
StringBuilderback to aStringusingsb.toString()and return it.
Walkthrough
This approach avoids the pitfalls of string concatenation by using a mutable StringBuilder. We first initialize a StringBuilder with the input string. This takes O(N) time. Then, we iterate through the odd indices of the StringBuilder. For each odd index i, we calculate the shifted character based on the character at i-1 and the digit at i. The setCharAt() method allows us to update the character at a specific index in O(1) time on average. Finally, we convert the StringBuilder back to a string, which takes O(N) time. This results in an overall linear time complexity.
Here is the implementation:
class Solution { public String replaceDigits(String s) { StringBuilder sb = new StringBuilder(s); for (int i = 1; i < s.length(); i += 2) { char prevChar = sb.charAt(i - 1); int shift = sb.charAt(i) - '0'; sb.setCharAt(i, (char) (prevChar + shift)); } return sb.toString(); }}Complexity
Time
O(N), where N is the length of the string. Initialization, iteration, and final conversion to a string all take linear time.
Space
O(N), where N is the length of the string. This space is used to store the `StringBuilder`'s internal character array.
Trade-offs
Pros
Efficient with O(N) time complexity.
This is the standard and idiomatic way to build or modify strings in Java.
Reduces memory churn compared to the brute-force approach.
Cons
Introduces a dependency on the
StringBuilderclass, which might be slightly more overhead than a simple character array.
This approach is asymptotically equivalent to using a StringBuilder but operates on a more fundamental char array. The string is first converted to an array of characters. The array is then modified in-place. Finally, a new string is constructed from the modified array. This is one of the most performant ways to solve the problem in Java.
Algorithm
- Convert the input string
sinto a character array,chars. - Iterate through the
charsarray, focusing on the odd indices. A loop starting ati = 1and incrementing by 2 (i += 2) is suitable. - For each odd index
i:- The preceding character is
chars[i-1]. - The shift amount is the integer value of the digit
chars[i], which ischars[i] - '0'. - Calculate the new character:
(char)(chars[i-1] + (chars[i] - '0')). - Update the array at index
iwith this new character:chars[i] = ....
- The preceding character is
- After the loop completes, create a new string from the modified character array and return it.
Walkthrough
By converting the string to a char[], we can directly manipulate the individual characters. The toCharArray() method creates a copy of the string's characters, taking O(N) time and space. We then iterate through this array, which is very fast. For each odd index i, we read the character at i-1 and the digit at i, compute the new character, and overwrite the element at chars[i]. This update is an O(1) operation. After the loop, we construct a new String from the modified char[], which also takes O(N) time. The overall performance is excellent and on par with the StringBuilder approach, sometimes even slightly faster due to less overhead.
Here is the implementation:
class Solution { public String replaceDigits(String s) { char[] chars = s.toCharArray(); for (int i = 1; i < chars.length; i += 2) { // The shift value is the numeric value of the character at index i. // e.g., '1' becomes 1. int shift = chars[i] - '0'; // The character to be shifted is at the previous index i-1. char prevChar = chars[i - 1]; // Perform the shift and update the character array. chars[i] = (char) (prevChar + shift); } return new String(chars); }}Complexity
Time
O(N), where N is the length of the string. The process involves `toCharArray()` (O(N)), a single pass over the array (O(N)), and `new String(char[])` (O(N)), resulting in a linear time complexity.
Space
O(N), where N is the length of the string. This space is required for the character array `chars`.
Trade-offs
Pros
Optimal time complexity of O(N).
Potentially the fastest implementation due to direct array manipulation and minimal overhead.
Efficient memory usage.
Cons
Requires manual conversion to and from a character array, which can feel slightly less object-oriented than using
StringBuilder.
Solutions
Solution
class Solution {public String replaceDigits(String s) { char[] cs = s.toCharArray(); for (int i = 1; i < cs.length; i += 2) { cs[i] = (char)(cs[i - 1] + (cs[i] - '0')); } return String.valueOf(cs); }}class Solution {public: string replaceDigits(string s) { int n = s.size(); for (int i = 1; i < n; i += 2) { s[i] = s[i - 1] + s[i] - '0'; } return s; }};class Solution: def replaceDigits(self, s: str) -> str: s = list(s) for i in range(1, len(s), 2): s[i] = chr(ord(s[i - 1]) + int(s[i])) return '' . join(s)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.