# Replace All Digits with Characters
**Difficulty:** EASY
[External](https://leetcode.com/problems/replace-all-digits-with-characters)
Canonical: https://scaleengineer.com/dsa/problems/replace-all-digits-with-characters
**Data structures:** String
---
## 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'` 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
## Brute Force with String Concatenation
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.
**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.
**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.
### Explanation
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:
```java
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;
    }
}
```
### 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.

## Efficient Approach with StringBuilder
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.
**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.
**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 `StringBuilder` class, which might be slightly more overhead than a simple character array.
### Explanation
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:
```java
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();
    }
}
```
### Algorithm
- Create a `StringBuilder` instance, initializing it with the input string `s`.
- Iterate through the string using a loop that only visits the odd indices. The loop should start at `i = 1` and 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 the `StringBuilder` to replace the digit at index `i` with the new character.
- After the loop, convert the `StringBuilder` back to a `String` using `sb.toString()` and return it.

## Optimal Approach with 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.
**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`.
**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`.
### Explanation
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:
```java
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);
    }
}
```
### Algorithm
- Convert the input string `s` into a character array, `chars`.
- Iterate through the `chars` array, focusing on the odd indices. A loop starting at `i = 1` and 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 is `chars[i] - '0'`.
    - Calculate the new character: `(char)(chars[i-1] + (chars[i] - '0'))`.
    - Update the array at index `i` with this new character: `chars[i] = ...`.
- After the loop completes, create a new string from the modified character array and return it.

# Solutions
### Java

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

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```