Scale Engineer

Replace All Digits with Characters

Easy
#1684Time: 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.
Data structures
String

Prompt

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' and shift('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 <= 100
  • s consists only of lowercase English letters and digits.
  • shift(s[i-1], s[i]) <= 'z' for all odd indices i.

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 s from the first character to the last, using an index i.
  • If the current index i is even, it means s.charAt(i) is a letter. Append this character directly to the result string.
  • If the current index i is odd, it means s.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 newChar to the result string.
  • After the loop finishes, return the result string.

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 String and StringBuilder objects, leading to high memory churn and frequent garbage collection.

Solutions

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);  }}

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.

← Previous

Previous problem

Next →

Next problem