Domain 1EasyCORE

Decrypt String from Alphabet to Integer Mapping

The problem requires mapping a string `s` formed by digits (`'0'` - `'9'`) and `'#'` characters into English lowercase letters. The mapping rules are: - Characters `'a'` to `'i'` are represented by `'1'` to `'9'`. - Characters `'j'` to `'z'` are represented by `'10#'` to `'26#'`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1309. Decrypt String from Alphabet to Integer Mapping

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 77.8%


Problem Breakdown

The problem requires mapping a string s formed by digits ('0' - '9') and '#' characters into English lowercase letters. The mapping rules are:

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

The task is to return the string formed after applying this mapping. The input string s will always be valid, ensuring a unique mapping exists.

Inputs:

  • A string s containing digits and '#'.

Outputs:

  • A string representing the mapped English lowercase letters.

Implicit Constraints/Edge Cases:

  • The string length is between 1 and 1000.
  • The input will always be valid, so no need to handle invalid inputs.
  • No duplicates or negative numbers are involved.
  • Overflow is not a concern due to the constraints.

Intuition

A brute-force approach would involve checking every possible substring of s for the presence of '#' and mapping accordingly. However, this would be inefficient in terms of both time and space complexity, especially given the string length constraint.

The key insight is to recognize that we can process the string from right to left. This allows us to handle the two-character mappings ('10#' to '26#') before processing single-digit mappings ('1' to '9'). By doing so, we ensure that each character or substring is processed only once.

Approach

  1. Initialize an empty list result to store the mapped characters.
  2. Use a pointer i starting from the end of the string s.
  3. While i is greater than or equal to 0:
    • If the current character s[i] is '#', it indicates a two-character mapping:
      • Extract the substring s[i-2:i] (two characters before '#').
      • Convert this substring to an integer and map it to the corresponding character.
      • Append the character to result.
      • Move the pointer i back by 3 positions (i -= 3).
    • Otherwise, it’s a single-digit mapping:
      • Convert the current character s[i] to an integer and map it to the corresponding character.
      • Append the character to result.
      • Move the pointer i back by 1 position (i -= 1).
  4. Reverse the result list to get the correct order of characters.
  5. Join the characters in result to form the final string and return it.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string s. Each character or substring is processed exactly once.
  • Space Complexity: O(n), for storing the result list, which can be as large as the input string.

Solution

def freqAlphabets(s: str) -> str:
    result = []
    i = len(s) - 1
    
    while i >= 0:
        if s[i] == '#':
            # Two-character mapping
            num = int(s[i-2:i])
            result.append(chr(num + ord('a') - 1))
            i -= 3
        else:
            # Single-digit mapping
            num = int(s[i])
            result.append(chr(num + ord('a') - 1))
            i -= 1
    
    return ''.join(result[::-1])

Edge Cases Handled

  • Single-character mappings: The code correctly handles single-digit numbers by converting them to the corresponding characters.
  • Two-character mappings: The code correctly identifies and processes substrings ending with '#' to map them to the appropriate characters.
  • Mixed mappings: The code can handle strings that contain both single and two-character mappings, processing them in the correct order from right to left.