Decrypt String from Alphabet to Integer Mapping

Difficulty: Easy | Acceptance: 80.60% | Paid: No Topics: String

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 of s to English letters always exists.

• Examples
• Constraints
• Reverse Iteration
• Forward Iteration with Lookahead
• Hash Map Lookup
• Regular Expression

Examples

Input: s = "10#11#12"
Output: "jkab"
Explanation: "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "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.

Reverse Iteration

Intuition Scan the string from right to left. When we encounter ’#’, we know it’s part of a two-digit number (10-26), so we take the two digits before it. Otherwise, it’s a single digit (1-9).

Steps

• Start from the end of the string
• If current character is ’#’, extract the two digits before it and convert to letter (j-z)
• Otherwise, take the single digit and convert to letter (a-i)
• Build the result in reverse order, then reverse at the end

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

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the result string
• Notes: Requires reversing the result at the end, but avoids lookahead checks

Forward Iteration with Lookahead

Intuition Scan from left to right and look ahead to check if there’s a ’#’ two positions ahead. If yes, it’s a two-digit encoded character; otherwise, it’s a single digit.

Steps

• Iterate through the string from left to right
• Check if position i+2 exists and contains ’#‘
• If yes, take two digits and skip 3 positions
• Otherwise, take one digit and skip 1 position

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

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the result string
• Notes: Builds result in correct order without needing to reverse

Hash Map Lookup

Intuition Pre-build a mapping from all possible encoded strings (“1” to “9” and “10#” to “26#”) to their corresponding letters. Then iterate through the string and use the map for O(1) lookups.

Steps

• Create a hash map with keys “1”-“9” mapping to “a”-“i” and “10#”-“26#” mapping to “j”-“z”
• Iterate through the string, checking for ’#’ two positions ahead
• Use the map to get the corresponding letter for each encoded segment

class Solution:
    def freqAlphabets(self, s: str) -> str:
        mapping = {}
        for i in range(1, 10):
            mapping[str(i)] = chr(ord('a') + i - 1)
        for i in range(10, 27):
            mapping[str(i) + '#'] = chr(ord('a') + i - 1)
        
        result = []
        i = 0
        n = len(s)
        while i < n:
            if i + 2 < n and s[i + 2] == '#':
                result.append(mapping[s[i:i+3]])
                i += 3
            else:
                result.append(mapping[s[i]])
                i += 1
        return ''.join(result)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the result string plus O(26) for the hash map
• Notes: Uses extra space for the map but provides clean, readable code with O(1) lookups

Regular Expression

Intuition Use regex pattern matching to find all encoded segments (either single digit or digit-digit-#) and replace each with its corresponding letter in one pass.

Steps

• Define a regex pattern that matches either a single digit or two digits followed by ’#‘
• Apply the pattern to find all matches in the string
• For each match, convert to the corresponding letter

import re

class Solution:
    def freqAlphabets(self, s: str) -> str:
        def replace_match(match):
            num = int(match.group(0).replace('#', ''))
            return chr(ord('a') + num - 1)
        
        return re.sub(r'\d\d#|\d', replace_match, s)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the result string
• Notes: Most concise solution in languages with good regex support; C++ uses forward iteration as regex approach is less idiomatic