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.

Examples

Example 1

1
2
3
4
5
6
7


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

Example 2

1
2
3
4
5
6


    
    
    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.

Solution

Method 1 – Reverse Traversal and Greedy Decoding

Intuition

We can decode the string by scanning from right to left. If we see a ‘#’, we know the previous two digits form a number from 10 to 26, mapping to ‘j’ to ‘z’. Otherwise, each single digit maps to ‘a’ to ‘i’.

Approach

  1. Initialize an empty result list.
  2. Start from the end of the string and move left.
  3. If the current character is ‘#’, take the previous two digits, convert to a number, and map to a letter (‘j’ to ‘z’). Move the pointer back by 3.
  4. If not ‘#’, map the single digit to a letter (‘a’ to ‘i’). Move the pointer back by 1.
  5. Reverse the result and join to form the answer string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    string freqAlphabets(string s) {
        string ans;
        int i = s.size() - 1;
        while (i >= 0) {
            if (s[i] == '#') {
                int num = (s[i-2] - '0') * 10 + (s[i-1] - '0');
                ans += (char)('a' + num - 1);
                i -= 3;
            } else {
                ans += (char)('a' + (s[i] - '0') - 1);
                i--;
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func freqAlphabets(s string) string {
    ans := make([]byte, 0, len(s))
    i := len(s) - 1
    for i >= 0 {
        if s[i] == '#' {
            num := (s[i-2]-'0')*10 + (s[i-1]-'0')
            ans = append(ans, byte('a'+num-1))
            i -= 3
        } else {
            ans = append(ans, byte('a'+(s[i]-'0')-1))
            i--
        }
    }
    // reverse
    for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
        ans[l], ans[r] = ans[r], ans[l]
    }
    return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public String freqAlphabets(String s) {
        StringBuilder ans = new StringBuilder();
        int i = s.length() - 1;
        while (i >= 0) {
            if (s.charAt(i) == '#') {
                int num = (s.charAt(i-2) - '0') * 10 + (s.charAt(i-1) - '0');
                ans.append((char)('a' + num - 1));
                i -= 3;
            } else {
                ans.append((char)('a' + (s.charAt(i) - '0') - 1));
                i--;
            }
        }
        return ans.reverse().toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun freqAlphabets(s: String): String {
        val ans = StringBuilder()
        var i = s.length - 1
        while (i >= 0) {
            if (s[i] == '#') {
                val num = (s[i-2] - '0') * 10 + (s[i-1] - '0')
                ans.append('a' + num - 1)
                i -= 3
            } else {
                ans.append('a' + (s[i] - '0') - 1)
                i--
            }
        }
        return ans.reverse().toString()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def freqAlphabets(self, s: str) -> str:
        ans: list[str] = []
        i: int = len(s) - 1
        while i >= 0:
            if s[i] == '#':
                num = int(s[i-2:i])
                ans.append(chr(ord('a') + num - 1))
                i -= 3
            else:
                ans.append(chr(ord('a') + int(s[i]) - 1))
                i -= 1
        return ''.join(ans[::-1])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn freq_alphabets(s: String) -> String {
        let bytes = s.as_bytes();
        let mut ans = Vec::with_capacity(bytes.len());
        let mut i = bytes.len() as i32 - 1;
        while i >= 0 {
            if bytes[i as usize] == b'#' {
                let num = (bytes[(i-2) as usize] - b'0') * 10 + (bytes[(i-1) as usize] - b'0');
                ans.push((b'a' + num - 1) as char);
                i -= 3;
            } else {
                ans.push((b'a' + (bytes[i as usize] - b'0') - 1) as char);
                i -= 1;
            }
        }
        ans.reverse();
        ans.into_iter().collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    freqAlphabets(s: string): string {
        let ans: string[] = [];
        let i = s.length - 1;
        while (i >= 0) {
            if (s[i] === '#') {
                const num = parseInt(s.slice(i-2, i));
                ans.push(String.fromCharCode('a'.charCodeAt(0) + num - 1));
                i -= 3;
            } else {
                ans.push(String.fromCharCode('a'.charCodeAt(0) + parseInt(s[i]) - 1));
                i--;
            }
        }
        return ans.reverse().join('');
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, since we scan each character once.
  • 🧺 Space complexity: O(n), for the answer string.