Problem Description

Given a string s representing a mapping from integers to lowercase English letters, your task is to decrypt it into the original string. The mapping is defined as follows:

• Characters from 'a' to 'i' are represented by '1' to '9'.
• Characters from 'j' to 'z' are represented by '10#' to '26#'.

The string s consists of digits and the '#' character. Each mapping is non-overlapping and there is exactly one way to decode s.

Example:
Input: s = "10#11#12"
Output: "jkab"

Constraints:

• 1 <= s.length <= 1000
• s contains only digits and '#' characters
• There is exactly one valid way to decrypt s

Thought Process

At first glance, this problem looks like a string parsing task. The key challenge is to recognize two types of encodings: single digits ('1' to '9') and two digits followed by '#' ('10#' to '26#').

A brute-force approach would be to check every possible substring, but since there is only one valid way to decode the string, we can process it from left to right (or right to left) and look for '#' characters to identify two-digit mappings.

We realize that whenever we see a '#', the two digits before it represent a letter from 'j' to 'z'. Otherwise, each digit stands alone as a letter from 'a' to 'i'.

By shifting from checking all possibilities to simply looking for '#' and processing accordingly, we can make the solution much more efficient and straightforward.

Solution Approach

Here's how we can systematically solve the problem:

1. Initialize an empty result string. We'll build our decrypted message character by character.
2. Process the input string from left to right:
   • If the current character is part of a two-digit mapping (i.e., the next two characters form a number and the third is '#'), parse the two digits, convert them to a letter, and move the pointer ahead by 3.
   • Otherwise, parse the single digit, convert it to a letter, and move the pointer ahead by 1.
3. Character conversion: To convert a number to a letter, use the fact that 'a' is at position 1, so chr(int(num) + ord('a') - 1) gives the correct character.
4. Continue until the end of the string.
5. Return the result string.

This approach is efficient and clear, using simple string manipulation and character arithmetic.

Example Walkthrough

Let's walk through the example s = "10#11#12" step by step:

1. Start at index 0. At index 2, there's a '#', so s[0:2] is "10". Convert 10 to 'j'. Move to index 3.
2. At index 3, again, at index 5, there's a '#'. s[3:5] is "11". Convert 11 to 'k'. Move to index 6.
3. Now at index 6, there's no '#' ahead, so process s[6] which is '1'. Convert 1 to 'a'. Move to index 7.
4. At index 7, process '2'. Convert 2 to 'b'. Move to index 8 (end).

The result is "jkab".

Time and Space Complexity

Brute-force Approach: If we tried every possible substring split, time complexity would be exponential (O(2^n)), but the problem guarantees one valid decoding.

Optimized Approach: Our solution processes each character at most once, so

• Time Complexity: O(n), where n is the length of s.
• Space Complexity: O(n) for the output string (ignoring input and output, the algorithm itself is O(1) space).

Summary

To solve the "Decrypt String from Alphabet to Integer Mapping" problem, we leverage the unique mapping pattern and the guarantee of a single valid solution. By scanning for '#' characters and decoding accordingly, we create a simple, efficient algorithm. The key insight is recognizing the two types of encodings and using straightforward string and character operations to decrypt the message.

Code Implementation

class Solution:
    def freqAlphabets(self, s: str) -> str:
        res = []
        i = 0
        while i < len(s):
            if i + 2 < len(s) and s[i + 2] == '#':
                num = int(s[i:i+2])
                res.append(chr(num + ord('a') - 1))
                i += 3
            else:
                num = int(s[i])
                res.append(chr(num + ord('a') - 1))
                i += 1
        return ''.join(res)
      

class Solution {
public:
    string freqAlphabets(string s) {
        string res = "";
        int i = 0, n = s.size();
        while (i < n) {
            if (i + 2 < n && s[i + 2] == '#') {
                int num = stoi(s.substr(i, 2));
                res += (char)('a' + num - 1);
                i += 3;
            } else {
                int num = s[i] - '0';
                res += (char)('a' + num - 1);
                i += 1;
            }
        }
        return res;
    }
};
      

class Solution {
    public String freqAlphabets(String s) {
        StringBuilder res = new StringBuilder();
        int i = 0, n = s.length();
        while (i < n) {
            if (i + 2 < n && s.charAt(i + 2) == '#') {
                int num = Integer.parseInt(s.substring(i, i + 2));
                res.append((char)('a' + num - 1));
                i += 3;
            } else {
                int num = s.charAt(i) - '0';
                res.append((char)('a' + num - 1));
                i += 1;
            }
        }
        return res.toString();
    }
}
      

var freqAlphabets = function(s) {
    let res = "";
    let i = 0;
    while (i < s.length) {
        if (i + 2 < s.length && s[i + 2] === '#') {
            let num = parseInt(s.substring(i, i + 2), 10);
            res += String.fromCharCode(96 + num);
            i += 3;
        } else {
            let num = parseInt(s[i], 10);
            res += String.fromCharCode(96 + num);
            i += 1;
        }
    }
    return res;
};