Decrypt String from Alphabet to Integer Mapping solution and explanation
Google
9 more videos on this problem
Decrypt String from Alphabet to Integer Mapping (Leetcode 1309)Coding Interviews · 15:00 · 2K views
1309. Decrypt String from Alphabet to Integer Mapping || Java || Easy explanation || HindiCoding Sphere · 10:05 · 2K views
Decrypt String from Alphabet to Integer Mapping (LeetCode 1309)BitsToBytes · 13:49 · 1K views
Leetcode 1309. Decrypt String from Alphabet to Integer Mapping PythonTechZoo · 4:00 · 1K views
LeetCode 1309. Decrypt String from Alphabet to Integer Mapping Solution Explained - JavaAlgorithms and Data Structures Course · 10:26 · 978 views
Leetcode 1309: Decrypt String from Alphabet to Integer Mapping (Leetcode easy)Algorithms Casts · 24:37 · 903 views
1309 Decrypt String from Alphabet to Integer Mapping | Complete Playlist of Easy Level QuestionsEduEverybody · 11:03 · 820 views
Leetcode1309. Decrypt String from Alphabet to Integer Mapping (Solution + Explanation)ultcode · 6:16 · 713 views
LeetCode#1309 Decrypt String from Alphabet to Integer Mapping - PythonCodeJulian · 1:59 · 585 views
leetcode - 1309 Decrypt String from Alphabet to Integer Mapping Explanation & SolutionlitCode · 16:14 · 506 views
The 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 <= 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.
def decrypt_string(s: str) -> str:
result = []
i = 0
while i < len(s):
if i + 2 < len(s) and s[i + 2] == '#':
result.append(chr(int(s[i:i + 2]) + ord('a') - 1))
i += 3
else:
result.append(chr(int(s[i]) + ord('a') - 1))
i += 1
return ''.join(result)
# Example usage
s = "10#11#12"
print(decrypt_string(s))public class DecryptString {
public static String decrypt(String s) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (i + 2 < s.length() && s.charAt(i + 2) == '#') {
int num = Integer.parseInt(s.substring(i, i + 2));
result.append((char) ('a' + num - 1));
i += 2;
} else {
result.append((char) ('a' + (s.charAt(i) - '0') - 1));
}
}
return result.toString();
}
public static void main(String[] args) {
String s = "10#11#12";
System.out.println(decrypt(s));
}
}#include <iostream>
#include <string>
std::string decryptString(std::string s) {
std::string result = "";
int i = 0;
while (i < s.length()) {
if (i + 2 < s.length() && s[i + 2] == '#') {
int num = (s[i] - '0') * 10 + (s[i + 1] - '0');
result += 'a' + num - 1;
i += 3;
} else {
result += 'a' + (s[i] - '0') - 1;
i++;
}
}
return result;
}
int main() {
std::string s = "1326#";
std::cout << decryptString(s) << std::endl;
return 0;
}function decryptString(s) {
let result = '';
for (let i = 0; i < s.length; i++) {
if (i + 2 < s.length && s[i + 2] === '#') {
let num = parseInt(s.substring(i, i + 2), 10);
result += String.fromCharCode(num + 96);
i += 2;
} else {
result += String.fromCharCode(parseInt(s[i], 10) + 96);
}
}
return result;
}
// Example usage
let s = "10#11#12";
console.log(decryptString(s));#include <stdio.h>
#include <string.h>
void decrypt(char *s, char *result) {
int i = 0, j = 0, len = strlen(s);
while (i < len) {
if (i + 2 < len && s[i + 2] == '#') {
int num = (s[i] - '0') * 10 + (s[i + 1] - '0');
result[j++] = 'a' + num - 1;
i += 3;
} else {
result[j++] = 'a' + (s[i] - '0') - 1;
i++;
}
}
result[j] = '\0';
}
int main() {
char s[] = "10#11#12";
char result[100];
decrypt(s, result);
printf("%s\n", result);
return 0;
}using System;
class DecryptString {
public static string Decrypt(string s) {
var result = new System.Text.StringBuilder();
for (int i = 0; i < s.Length; i++) {
if (i + 2 < s.Length && s[i + 2] == '#') {
int num = int.Parse(s.Substring(i, 2));
result.Append((char)('a' + num - 1));
i += 2;
} else {
result.Append((char)('a' + (s[i] - '0') - 1));
}
}
return result.ToString();
}
static void Main() {
string s = "1326#";
Console.WriteLine(Decrypt(s));
}
}The code leverages a list to store the resultant characters, iterating through each index in the input string, and converting substrings to the corresponding characters.
Time Complexity: O(n).
Space Complexity: O(n).
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.
def decrypt_string_reverse(s: str) -> str:
result = []
i = len(s) - 1
while i >= 0:
if s[i] == '#':
result.append(chr(int(s[i-2:i]) + ord('a') - 1))
i -= 3
else:
result.append(chr(int(s[i]) + ord('a') - 1))
i -= 1
return ''.join(result[::-1])
# Example usage
s = "1326#"
print(decrypt_string_reverse(s))public class DecryptReverse {
public static String decryptFromEnd(String s) {
StringBuilder result = new StringBuilder();
for (int i = s.length() - 1; i >= 0; ) {
if (s.charAt(i) == '#') {
int num = Integer.parseInt(s.substring(i-2, i));
result.append((char) ('a' + num - 1));
i -= 3;
} else {
result.append((char) ('a' + (s.charAt(i) - '0') - 1));
i--;
}
}
return result.reverse().toString();
}
public static void main(String[] args) {
String s = "10#11#12";
System.out.println(decryptFromEnd(s));
}
}#include <iostream>
#include <algorithm>
#include <string>
std::string decryptStringReverse(std::string s) {
std::string result = "";
for (int i = s.length() - 1; i >= 0; ) {
if (s[i] == '#') {
int num = (s[i-2] - '0') * 10 + (s[i-1] - '0');
result += 'a' + num - 1;
i -= 3;
} else {
result += 'a' + (s[i] - '0') - 1;
i--;
}
}
std::reverse(result.begin(), result.end());
return result;
}
int main() {
std::string s = "1326#";
std::cout << decryptStringReverse(s) << std::endl;
return 0;
}function decryptStringReverse(s) {
let result = '';
for (let i = s.length - 1; i >= 0; ) {
if (s[i] === '#') {
let num = parseInt(s.substring(i-2, i), 10);
result += String.fromCharCode(num + 96);
i -= 3;
} else {
result += String.fromCharCode(parseInt(s[i], 10) + 96);
i--;
}
}
return result.split('').reverse().join('');
}
// Example usage
let s = "1326#";
console.log(decryptStringReverse(s));#include <stdio.h>
#include <string.h>
void decrypt_reverse(char *s, char *result) {
int j = 0;
int i = strlen(s) - 1;
while (i >= 0) {
if (s[i] == '#') {
int num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
result[j++] = 'a' + num - 1;
i -= 3;
} else {
result[j++] = 'a' + (s[i] - '0') - 1;
i--;
}
}
for (int k = 0; k < j / 2; k++) {
char temp = result[k];
result[k] = result[j - 1 - k];
result[j - 1 - k] = temp;
}
result[j] = '\0';
}
int main() {
char s[] = "1326#";
char result[100];
decrypt_reverse(s, result);
printf("%s\n", result);
return 0;
}using System;
class ReverseDecrypt {
public static string DecryptReverse(string s) {
var result = new System.Text.StringBuilder();
for (int i = s.Length - 1; i >= 0; ) {
if (s[i] == '#') {
int num = int.Parse(s.Substring(i-2, 2));
result.Append((char)('a' + num - 1));
i -= 3;
} else {
result.Append((char)('a' + (s[i] - '0') - 1));
i--;
}
}
char[] resultArray = result.ToString().ToCharArray();
Array.Reverse(resultArray);
return new string(resultArray);
}
static void Main() {
string s = "10#11#12";
Console.WriteLine(DecryptReverse(s));
}
}Parses the string in reverse, using list operations to aptly append decoded characters. The list is reversed at the end.
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.
function freqAlphabets(s: string): string {
const ans: string[] = [];
for (let i = 0, n = s.length; i < n; ) {
if (i + 2 < n && s[i + 2] === '#') {
ans.push(String.fromCharCode(96 + +s.slice(i, i + 2)));
i += 3;
} else {
ans.push(String.fromCharCode(96 + +s[i]));
i++;
}
}
return ans.join('');
}func freqAlphabets(s string) string {
var ans []byte
for i, n := 0, len(s); i < n; {
if i+2 < n && s[i+2] == '#' {
num := (int(s[i])-'0')*10 + int(s[i+1]) - '0'
ans = append(ans, byte(num+int('a')-1))
i += 3
} else {
num := int(s[i]) - '0'
ans = append(ans, byte(num+int('a')-1))
i += 1
}
}
return string(ans)
}impl Solution {
pub fn freq_alphabets(s: String) -> String {
let s = s.as_bytes();
let mut ans = String::new();
let mut i = 0;
let n = s.len();
while i < n {
if i + 2 < n && s[i + 2] == b'#' {
let num = (s[i] - b'0') * 10 + (s[i + 1] - b'0');
ans.push((96 + num) as char);
i += 3;
} else {
let num = s[i] - b'0';
ans.push((96 + num) as char);
i += 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointer Approach | Time Complexity: O(n). |
| Reverse Parsing Approach | Time Complexity: O(n). |
| Simulation | – |
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 |
Frequently asked questions
Is Decrypt String from Alphabet to Integer Mapping easy or hard?
The problem is classified as Easy on LeetCode with an acceptance rate above 80%. It mainly tests careful string scanning and correct handling of the '#'-based two-digit encoding pattern.
Decrypt String from Alphabet to Integer Mapping Python/Java solution
In Python or Java, iterate through the string and detect whether a '#' indicates a two-digit number. Convert the numeric value to a character using ASCII arithmetic such as 'a' + value - 1. The same O(n) logic works consistently across Python, Java, C++, and JavaScript.
How to solve Decrypt String from Alphabet to Integer Mapping in O(n)?
Perform a single linear scan of the string. If you encounter a pattern where the third character ahead is '#', parse the first two digits as a number from 10 to 26 and convert it to a letter. Otherwise convert the current single digit to a character. Continue until the entire string is processed.
What is the best approach for Decrypt String from Alphabet to Integer Mapping?
The two pointer single-pass scan is typically the best approach. You iterate through the string and check if the next two characters form a number followed by '#'. This allows decoding both single-digit and two-digit mappings in O(n) time with O(1) extra space.
Is Decrypt String from Alphabet to Integer Mapping asked at Google/Amazon/Meta?
Problems involving string parsing and encoded mappings are common in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the pattern recognition and string manipulation techniques are frequently tested.
What data structure is used in Decrypt String from Alphabet to Integer Mapping?
The problem mainly relies on string traversal and ASCII character conversion. No complex data structures are required; a pointer index and a result string builder are sufficient to decode the mapping efficiently.
What is the time complexity of Decrypt String from Alphabet to Integer Mapping?
Both common solutions run in O(n) time where n is the length of the input string. Each character is processed at most once. Space complexity is O(1) excluding the output string since only a few variables are used during parsing.