algoadvance

Leetcode 1844. Replace All Digits with Characters

Problem Statement

1844. Replace All Digits with Characters

You are given a 0-indexed string s that has lowercase English letters in its even indices and digits in its odd indices.

There is a function defined as shift(c, x) where c is a character and x is a digit, that shifts c forward in the alphabet by x positions.

• For example, shift('a', 1) = 'b' and shift('x', 3) = 'a'.

Replace every digit in s with shift(s[i-1], s[i]).

Return the modified string s.

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'

Clarifying Questions

1. Are all the characters in the string lowercase English letters and digits?
   • Yes, as per the problem statement.
2. Would input strings always be valid as per the given constraints?
   • Yes, you can assume the input will conform to the specified format (letters at even indices and digits at odd indices).
3. Would there be any scenarios where input string is empty?
   • No, according to the examples provided, we can infer the input string is non-empty.

Strategy

To solve this problem, follow these steps:

1. Initialize a StringBuilder to construct the final string.
2. Iterate through the given string s.
3. For characters at even indices, append them directly to the StringBuilder.
4. For digits at odd indices:
   • Convert the previous character (even index) and the current digit to the corresponding shifted character using the shift function.
   • Append the shifted character to the StringBuilder.
5. Convert the StringBuilder to a final string and return it.

Helper Method:

• shift(char c, int x): This method takes a character c and an integer x, then returns the character shifted x positions forward in the alphabet.

Code Implementation

public class ReplaceDigitsWithCharacters {
    public static void main(String[] args) {
        String s1 = "a1c1e1";
        String s2 = "a1b2c3d4e";
        
        System.out.println(replaceDigits(s1));  // Output: "abcdef"
        System.out.println(replaceDigits(s2));  // Output: "abbdcfdhe"
    }

    public static String replaceDigits(String s) {
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            if (i % 2 == 0) {
                result.append(currentChar);
            } else {
                int shiftValue = currentChar - '0';
                char previousChar = s.charAt(i - 1);
                char shiftedChar = shift(previousChar, shiftValue);
                result.append(shiftedChar);
            }
        }
        
        return result.toString();
    }

    private static char shift(char c, int x) {
        return (char) (c + x);
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the string s. We iterate through the string once.
• Space Complexity: O(n), due to the usage of StringBuilder to store the resulting string.

This solution is efficient for the given problem and adheres to the constraints provided.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?