LeetCode 1844 - Replace All Digits with Characters

LeetCode Problem 1844

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

In this problem, we are given a string s where characters at even indices are always lowercase English letters, and characters at odd indices are always digits.

The goal is to replace every digit with a new character computed from the character immediately before it. The operation is called shift(c, x), which means:

• Start from character c
• Move forward x positions in the alphabet
• Return the resulting character

For example:

• shift('a', 1) becomes 'b'
• shift('c', 2) becomes 'e'
• shift('x', 0) stays 'x'

The input string alternates between letters and digits in a predictable way:

• Even positions contain letters
• Odd positions contain digits

For every odd index i, we must:

1. Read the previous character s[i - 1]
2. Convert the digit s[i] into an integer
3. Shift the previous character forward by that amount
4. Replace the digit with the resulting character

Finally, we return the fully transformed string.

The constraints are very small:

• 1 <= s.length <= 100

This means efficiency is not a major concern, but we should still write clean and optimal code.

An important guarantee is:

• shift(s[i-1], s[i]) <= 'z'

This means we never need to worry about wrapping around the alphabet. Every shifted character will remain a valid lowercase English letter.

Some important edge cases include:

• A string of length 1, where no digits exist
• Digits equal to 0, where the character stays unchanged
• Multiple alternating letter-digit pairs
• Ensuring character arithmetic is handled correctly

Approaches

Brute Force Approach

A brute-force style solution would explicitly simulate the shift operation character by character.

For every digit:

1. Take the previous letter
2. Move forward one step at a time in the alphabet
3. Repeat until the digit count is exhausted
4. Replace the digit with the resulting letter

For example, shifting 'a' by 3 would involve:

• 'a' -> 'b'
• 'b' -> 'c'
• 'c' -> 'd'

This approach works correctly because it directly follows the definition of the shift operation. However, repeatedly moving one character at a time is unnecessary.

Even though the constraints are tiny, we can do better using character arithmetic.

Optimal Approach

The key observation is that characters are internally stored as ASCII or Unicode integer values.

For example:

• 'a' has value 97
• 'b' has value 98
• 'c' has value 99

So shifting a character by x positions is equivalent to:

new_character = chr(ord(character) + x)

This allows us to compute the shifted character in constant time.

The algorithm becomes straightforward:

1. Convert the string into a mutable array
2. Iterate through odd indices
3. Compute the shifted character directly
4. Replace the digit
5. Join the array back into a string

This is efficient, simple, and easy to implement.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * d)	O(n)	Simulates shifting one step at a time
Optimal	O(n)	O(n)	Uses direct character arithmetic

Here, n is the string length and d is the maximum digit value, at most 9.

Algorithm Walkthrough

1. Convert the input string into a list or array of characters.

Strings are immutable in Python, so converting to a list allows in-place modification. In Go, byte slices already support mutation. 2. Iterate through all odd indices.

Since the problem guarantees that odd indices contain digits, we only need to process positions 1, 3, 5, .... 3. For each odd index, read the previous character.

The character at i - 1 is guaranteed to be a lowercase letter. 4. Convert the digit character into an integer.

For example, '3' becomes 3. 5. Compute the shifted character.

Use character arithmetic:

shifted = chr(ord(previous_char) + digit)

6. Replace the digit with the shifted character.

This transforms the string in-place. 7. After processing all odd indices, join the characters back into a string and return it.

Why it works

The algorithm works because every digit at an odd index represents exactly how many positions to move forward from the previous character. Character arithmetic directly models this operation.

Since the problem guarantees that the shifted result never exceeds 'z', adding the digit value to the character code always produces a valid lowercase letter.

Each digit is processed independently, so replacing one digit never affects future computations.

Python Solution

class Solution:
    def replaceDigits(self, s: str) -> str:
        characters = list(s)

        for i in range(1, len(characters), 2):
            previous_char = characters[i - 1]
            digit = int(characters[i])

            shifted_char = chr(ord(previous_char) + digit)

            characters[i] = shifted_char

        return "".join(characters)

The implementation begins by converting the string into a list called characters. This is necessary because Python strings cannot be modified directly.

The loop starts at index 1 and increments by 2, ensuring that only odd indices are processed. At every odd index:

• characters[i - 1] gives the previous letter
• int(characters[i]) converts the digit character into an integer
• ord() converts the letter into its numeric ASCII value
• Adding the digit performs the shift
• chr() converts the numeric value back into a character

Finally, "".join(characters) reconstructs the transformed string.

Go Solution

func replaceDigits(s string) string {
    characters := []byte(s)

    for i := 1; i < len(characters); i += 2 {
        previousChar := characters[i-1]
        digit := characters[i] - '0'

        characters[i] = previousChar + digit
    }

    return string(characters)
}

The Go implementation uses a byte slice because strings in Go are immutable. Converting the string to []byte allows in-place updates.

Instead of ord() and chr(), Go can directly manipulate ASCII byte values. The digit conversion is done using:

digit := characters[i] - '0'

This converts a character like '3' into numeric value 3.

The shifted character is computed directly with byte arithmetic.

Worked Examples

Example 1

Input:

s = "a1c1e1"

Initial character array:

Index	Value
0	a
1	1
2	c
3	1
4	e
5	1

Step-by-step processing:

i	Previous Character	Digit	Shifted Character	Updated Array
1	a	1	b	a b c 1 e 1
3	c	1	d	a b c d e 1
5	e	1	f	a b c d e f

Final result:

"abcdef"

Example 2

Input:

s = "a1b2c3d4e"

Initial array:

Index	Value
0	a
1	1
2	b
3	2
4	c
5	3
6	d
7	4
8	e

Step-by-step processing:

i	Previous Character	Digit	Shifted Character	Updated Array
1	a	1	b	a b b 2 c 3 d 4 e
3	b	2	d	a b b d c 3 d 4 e
5	c	3	f	a b b d c f d 4 e
7	d	4	h	a b b d c f d h e

Final result:

"abbdcfdhe"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed at most once
Space	O(n)	A mutable character array is created

The algorithm iterates through the string once, processing only odd indices. Every operation inside the loop is constant time, so the total runtime is linear in the size of the input string.

The additional space comes from creating a mutable list or byte slice representation of the string.

Test Cases

solution = Solution()

# Provided example 1
assert solution.replaceDigits("a1c1e1") == "abcdef"

# Provided example 2
assert solution.replaceDigits("a1b2c3d4e") == "abbdcfdhe"

# Single character, no digits
assert solution.replaceDigits("a") == "a"

# Shift by zero
assert solution.replaceDigits("a0") == "aa"

# Multiple zero shifts
assert solution.replaceDigits("a0b0c0") == "aabbcc"

# Largest reasonable shift
assert solution.replaceDigits("x2") == "xz"

# Mixed shifts
assert solution.replaceDigits("m1n2") == "monp"

# Alternating letters and digits
assert solution.replaceDigits("c1d1e1f1") == "cddeeffg"

# Minimal valid alternating input
assert solution.replaceDigits("z0") == "zz"

# Consecutive transformations
assert solution.replaceDigits("a2c2e2") == "ccggee"

Test	Why
"a1c1e1"	Validates the first example
"a1b2c3d4e"	Validates varying shift amounts
"a"	Tests smallest possible input
"a0"	Tests zero shift behavior
"a0b0c0"	Tests repeated zero shifts
"x2"	Tests shifts near end of alphabet
"m1n2"	Tests mixed shift values
"c1d1e1f1"	Tests multiple sequential replacements
"z0"	Tests boundary letter with zero shift
"a2c2e2"	Tests repeated larger shifts

Edge Cases

One important edge case is a string of length 1. In this situation, the string contains only a letter and no digits. A buggy implementation might incorrectly assume that every string has at least one digit. This solution handles the case naturally because the loop over odd indices never executes.

Another important edge case is a digit value of 0. When shifting by zero, the resulting character should remain unchanged. For example, "a0" becomes "aa". The implementation handles this correctly because adding 0 to the character code leaves the character unchanged.

A third important edge case involves letters near the end of the alphabet, such as 'x', 'y', or 'z'. Incorrect implementations might accidentally exceed valid character ranges. The problem guarantees that shifted characters never go beyond 'z', so direct character arithmetic is always safe.

A final subtle edge case is ensuring that replacements do not interfere with future computations. Since each digit only depends on the character immediately before it, and even indices are never modified, processing from left to right remains correct throughout the algorithm.