# Decrypt String from Alphabet to Integer Mapping
**Difficulty:** EASY
[External](https://leetcode.com/problems/decrypt-string-from-alphabet-to-integer-mapping)
Canonical: https://scaleengineer.com/dsa/problems/decrypt-string-from-alphabet-to-integer-mapping
**Data structures:** String
---
## Problem
You are given a string `s` formed by digits and `'#'`. We want to map `s` to English lowercase characters as follows:

* Characters (`'a'` to `'i'`) are represented by (`'1'` to `'9'`) respectively.
* Characters (`'j'` to `'z'`) are represented by (`'10#'` to `'26#'`) respectively.

Return _the string formed after mapping_.

The test cases are generated so that a unique mapping will always exist.

**Example 1:**

**Input:** s = "10#11#12"
**Output:** "jkab"
**Explanation:** "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

**Example 2:**

**Input:** s = "1326#"
**Output:** "acz"

**Constraints:**

* `1 <= s.length <= 1000`
* `s` consists of digits and the `'#'` letter.
* `s` will be a valid string such that mapping is always possible.

# Approaches
## Iterating from Left to Right with Lookahead
This approach processes the input string from left to right. At each position, it looks ahead to determine whether the current mapping involves a single digit or a two-digit number followed by a '#' symbol. Based on this lookahead, it decodes the corresponding segment and appends the resulting character to a new string.
**Time:** O(N), where N is the length of the input string `s`. We traverse the string once from left to right. · **Space:** O(N) to store the result in a `StringBuilder`. The space required for the output string is proportional to the input string length, where N is the length of the input string `s`.
**Pros:** Intuitive and easy to understand as it processes the string in its natural reading order.; Efficient with linear time complexity.
**Cons:** Requires a lookahead check (`i + 2 < s.length()`), which adds a bit of complexity and a potential point of error if not handled carefully.
### Explanation
We can solve this problem by iterating through the string `s` using a pointer, let's say `i`. We build the result string using a `StringBuilder` for efficiency.
The core logic relies on looking ahead from the current position `i`. We check if the character at index `i + 2` is a '#'. This check must be done carefully to avoid going out of bounds.
If `s[i+2]` is indeed '#', it signifies a two-digit number from '10' to '26'. We parse the substring `s.substring(i, i+2)`, convert it to the corresponding character ('j' through 'z'), and advance our pointer `i` by 3.
If the lookahead condition is not met, it means `s[i]` represents a single-digit number from '1' to '9'. We parse this digit, convert it to its character ('a' through 'i'), and advance the pointer `i` by 1.
This process continues until the entire string is parsed.
```java
class Solution {
    public String freqAlphabets(String s) {
        StringBuilder result = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            if (i + 2 < s.length() && s.charAt(i + 2) == '#') {
                // Two-digit number with a '#'
                int num = Integer.parseInt(s.substring(i, i + 2));
                result.append((char) ('a' + num - 1));
                i += 3;
            } else {
                // Single-digit number
                int num = s.charAt(i) - '0';
                result.append((char) ('a' + num - 1));
                i += 1;
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` to store the decrypted string.
- Initialize a pointer `i` to 0.
- Iterate through the string with the pointer `i` as long as `i` is less than the string length.
- Inside the loop, check if `i + 2` is a valid index and if the character at `i + 2` is '#'.
- If it is, parse the two-digit number from `s.substring(i, i + 2)`, convert it to a character by the formula `(char)('a' + number - 1)`, append it to the result, and increment `i` by 3.
- Otherwise, parse the single digit at `s.charAt(i)`, convert it to a character, append it to the result, and increment `i` by 1.
- After the loop, convert the `StringBuilder` to a string and return it.

## Iterating from Right to Left
A more elegant and slightly more efficient approach is to iterate through the string from right to left. This method simplifies the logic by removing the need for lookaheads. When a '#' is encountered, we know it corresponds to the two preceding digits. Otherwise, the current character is a single-digit mapping. The resulting characters are collected and then reversed to form the final string.
**Time:** O(N), where N is the length of the input string `s`. The traversal is O(N), and reversing the `StringBuilder` is also O(N), leading to a total linear time complexity. · **Space:** O(N) to store the result in a `StringBuilder`. The space is proportional to the length of the input string, where N is the length of `s`.
**Pros:** More elegant and less error-prone as it avoids lookahead logic.; The logic at each step is simpler: the character at the current pointer dictates the action.; Highly efficient with linear time and space complexity.
**Cons:** Requires a final step to reverse the constructed string, which might be slightly less intuitive than building the string in the correct order from the start.
### Explanation
This approach processes the string `s` from its end towards the beginning. We use a pointer `i` initialized to `s.length() - 1`.
When the character at `s[i]` is '#', we know it's the marker for a two-digit number. The number is formed by the characters at `i-2` and `i-1`. We parse this number, find the corresponding character, and append it to our `StringBuilder`. We then move the pointer `i` back by 3 positions.
If the character at `s[i]` is a digit, it represents a single-digit number. We parse it, find the character, append it to the `StringBuilder`, and move the pointer `i` back by 1.
Since we are processing from right to left and appending to the `StringBuilder`, the resulting string will be in reverse order. Therefore, the final step is to reverse the `StringBuilder` before converting it to a string.
```java
class Solution {
    public String freqAlphabets(String s) {
        StringBuilder result = new StringBuilder();
        int i = s.length() - 1;
        while (i >= 0) {
            if (s.charAt(i) == '#') {
                // Two-digit number
                int num = Integer.parseInt(s.substring(i - 2, i));
                result.append((char) ('a' + num - 1));
                i -= 3;
            } else {
                // Single-digit number
                int num = s.charAt(i) - '0';
                result.append((char) ('a' + num - 1));
                i -= 1;
            }
        }
        return result.reverse().toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` to store the intermediate decrypted string.
- Initialize a pointer `i` to the last index of the string (`s.length() - 1`).
- Iterate backwards through the string with the pointer `i` as long as `i` is non-negative.
- Inside the loop, check if the character at `s.charAt(i)` is '#'.
- If it is, parse the two-digit number from `s.substring(i - 2, i)`, convert it to a character, append it to the result, and decrement `i` by 3.
- Otherwise, parse the single digit at `s.charAt(i)`, convert it to a character, append it to the result, and decrement `i` by 1.
- After the loop, reverse the `StringBuilder`.
- Convert the reversed `StringBuilder` to a string and return it.

# Solutions
### Java

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

```

### CPP

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

### Python

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

```