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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6
7

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.

Solution

Method 1 - Simple Iteration and Character Arithmetic

Intuition

For each odd index, replace the digit with the result of shifting the previous character by the digit’s value. This can be done in a single pass using character arithmetic.

Approach

  1. Convert the string to a list for mutability.
  2. For each odd index i, set s[i] = chr(ord(s[i-1]) + int(s[i])).
  3. Join and return the result.

Code

1
2
3
4
5
6
7
8
9

#include <string>
using namespace std;

string replaceDigits(string s) {
    for (int i = 1; i < s.size(); i += 2) {
        s[i] = s[i-1] + (s[i] - '0');
    }
    return s;
}
1
2
3
4
5
6
7

func replaceDigits(s string) string {
    arr := []byte(s)
    for i := 1; i < len(arr); i += 2 {
        arr[i] = arr[i-1] + arr[i] - '0'
    }
    return string(arr)
}
1
2
3
4
5
6
7
8
9

public class Solution {
    public 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);
    }
}
1
2
3
4
5
6
7

fun replaceDigits(s: String): String {
    val arr = s.toCharArray()
    for (i in 1 until arr.size step 2) {
        arr[i] = (arr[i-1] + (arr[i] - '0')).toChar()
    }
    return String(arr)
}
1
2
3
4
5

def replaceDigits(s: str) -> str:
    arr = list(s)
    for i in range(1, len(arr), 2):
        arr[i] = chr(ord(arr[i-1]) + int(arr[i]))
    return ''.join(arr)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

fn replace_digits(s: &str) -> String {
    let mut arr: Vec<char> = s.chars().collect();
    let n = arr.len();
    for i in (1..n).step_by(2) {
        let prev = arr[i-1] as u8;
        let shift = arr[i] as u8 - b'0';
        arr[i] = (prev + shift) as char;
    }
    arr.into_iter().collect()
}
1
2
3
4
5
6
7

function replaceDigits(s: string): string {
    const 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("");
}

Complexity

  • ⏰ Time complexity: O(N), where N is the length of s.
  • 🧺 Space complexity: O(N), for the output string.