Decrypt String from Alphabet to Integer Mapping - Solution & Explanation
Problem Statement
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 <= 1000sconsists of digits and the'#'letter.swill be a valid string such that mapping is always possible.
Approach Overview
Problem Overview: You receive a string where numbers represent letters: 1-9 map to a-i and 10#-26# map to j-z. The task is to decode the string and return the resulting alphabetic text. The main challenge is detecting when a number is part of a two-digit mapping followed by #.
Approach 1: Two Pointer Approach (Time: O(n), Space: O(1))
Scan the string from left to right while checking whether the current position begins a two-digit encoded pattern. If s[i+2] == '#', then the substring s[i:i+2] represents a number between 10 and 26. Convert that value to its corresponding character using ASCII arithmetic and move the pointer forward by three positions. Otherwise, treat the current single digit as a value between 1 and 9, convert it to a letter, and advance the pointer by one. This method works well because the encoding guarantees that two-digit values always include the # marker, making detection constant time. The algorithm processes each character at most once, giving O(n) time complexity with O(1) extra space besides the output string. This approach fits naturally when working with sequential scans over string problems.
Approach 2: Reverse Parsing Approach (Time: O(n), Space: O(1))
Instead of scanning forward, start from the end of the string and build the result in reverse. When the current character is #, read the previous two digits to form a number between 10 and 26. Convert it into the corresponding letter and move the pointer three steps backward. If the current character is a digit, it represents a single-digit mapping, so convert it directly and move back one step. Because the encoding marker # always appears after two-digit numbers, reverse parsing avoids lookahead checks and simplifies the logic. The runtime remains O(n) since every character is processed once, and the algorithm uses O(1) additional memory. This approach is a good example of efficient string parsing techniques.
Recommended for interviews: The forward two pointer approach is usually what interviewers expect. It clearly demonstrates that you recognize the # pattern and handle variable-length tokens in a single pass. Reverse parsing is equally efficient and sometimes simpler to implement, so mentioning it shows deeper understanding of string processing strategies.
Approach 1: Two Pointer Approach
This approach leverages a two-pointer system to parse the string. The primary idea is to iterate through the string from the start to the end, using a pointer. Whenever we encounter a digit, we first check if the next character is '#'. If it is, it implies that this is a two-digit number representing a letter from 'j' to 'z'. Otherwise, it's a single character mapping.
This solution uses a simple iteration over the string. It checks for a '#' character two positions away every time it processes a digit. If found, it processes as a two-digit number, otherwise as a single digit.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for storing the output string.
Approach 2: Reverse Parsing Approach
In this approach, the string is traversed from the end to the start. This helps in directly processing two-digit characters whenever a '#' is encountered. We will decode the string backwards.
The C solution iterates backwards, which simplifies handling two-digit directives (numbers followed by '#'). Post processing, the result is reversed to obtain the correct order.
Complexity
Time Complexity: O(n).
Space Complexity: O(n).
Approach 3: Simulation
We can directly simulate the process.
Traverse the string s. For the current index i, if i + 2 < n and s[i + 2] is #, then convert the substring formed by s[i] and s[i + 1] to an integer, add the ASCII value of a minus 1, convert it to a character, add it to the result array, and increment i by 3. Otherwise, convert s[i] to an integer, add the ASCII value of a minus 1, convert it to a character, add it to the result array, and increment i by 1.
Finally, convert the result array to a string and return it.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two Pointer Approach | Time Complexity: O(n), where n is the length of the string. |
| Reverse Parsing Approach | Time Complexity: O(n). |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Approach | O(n) | O(1) | Best general solution when scanning strings sequentially and detecting encoded patterns |
| Reverse Parsing Approach | O(n) | O(1) | Useful when backward parsing simplifies detection of multi-character tokens |
Video Solution
Decrypt String from Alphabet to Integer Mapping (Leetcode 1309) • Coding Interviews • 2,973 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Decrypt String from Alphabet to Integer Mapping easy or hard?
Decrypt String from Alphabet to Integer Mapping Python/Java solution
How to solve Decrypt String from Alphabet to Integer Mapping in O(n)?
What is the best approach for Decrypt String from Alphabet to Integer Mapping?
Is Decrypt String from Alphabet to Integer Mapping asked at Google/Amazon/Meta?
What data structure is used in Decrypt String from Alphabet to Integer Mapping?
What is the time complexity of Decrypt String from Alphabet to Integer Mapping?
Ready to solve this problem?
Practice Decrypt String from Alphabet to Integer Mapping with our built-in code editor and test cases.
Practice on FleetCode