Decrypt String from Alphabet to Integer Mapping
EasyPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach processes the input string from left to right. At each position, it looks ahead to determine whether the current mapping involves a single digit or a two-digit number followed by a '#' symbol. Based on this lookahead, it decodes the corresponding segment and appends the resulting character to a new string.
Algorithm
- Initialize an empty
StringBuilderto store the decrypted string. - Initialize a pointer
ito 0. - Iterate through the string with the pointer
ias long asiis less than the string length. - Inside the loop, check if
i + 2is a valid index and if the character ati + 2is '#'. - If it is, parse the two-digit number from
s.substring(i, i + 2), convert it to a character by the formula(char)('a' + number - 1), append it to the result, and incrementiby 3. - Otherwise, parse the single digit at
s.charAt(i), convert it to a character, append it to the result, and incrementiby 1. - After the loop, convert the
StringBuilderto a string and return it.
Walkthrough
We can solve this problem by iterating through the string s using a pointer, let's say i. We build the result string using a StringBuilder for efficiency.
The core logic relies on looking ahead from the current position i. We check if the character at index i + 2 is a '#'. This check must be done carefully to avoid going out of bounds.
If s[i+2] is indeed '#', it signifies a two-digit number from '10' to '26'. We parse the substring s.substring(i, i+2), convert it to the corresponding character ('j' through 'z'), and advance our pointer i by 3.
If the lookahead condition is not met, it means s[i] represents a single-digit number from '1' to '9'. We parse this digit, convert it to its character ('a' through 'i'), and advance the pointer i by 1.
This process continues until the entire string is parsed.
class Solution { public String freqAlphabets(String s) { StringBuilder result = new StringBuilder(); int i = 0; while (i < s.length()) { if (i + 2 < s.length() && s.charAt(i + 2) == '#') { // Two-digit number with a '#' int num = Integer.parseInt(s.substring(i, i + 2)); result.append((char) ('a' + num - 1)); i += 3; } else { // Single-digit number int num = s.charAt(i) - '0'; result.append((char) ('a' + num - 1)); i += 1; } } return result.toString(); }}Complexity
Time
O(N), where N is the length of the input string `s`. We traverse the string once from left to right.
Space
O(N) to store the result in a `StringBuilder`. The space required for the output string is proportional to the input string length, where N is the length of the input string `s`.
Trade-offs
Pros
Intuitive and easy to understand as it processes the string in its natural reading order.
Efficient with linear time complexity.
Cons
Requires a lookahead check (
i + 2 < s.length()), which adds a bit of complexity and a potential point of error if not handled carefully.
A more elegant and slightly more efficient approach is to iterate through the string from right to left. This method simplifies the logic by removing the need for lookaheads. When a '#' is encountered, we know it corresponds to the two preceding digits. Otherwise, the current character is a single-digit mapping. The resulting characters are collected and then reversed to form the final string.
Algorithm
- Initialize an empty
StringBuilderto store the intermediate decrypted string. - Initialize a pointer
ito the last index of the string (s.length() - 1). - Iterate backwards through the string with the pointer
ias long asiis non-negative. - Inside the loop, check if the character at
s.charAt(i)is '#'. - If it is, parse the two-digit number from
s.substring(i - 2, i), convert it to a character, append it to the result, and decrementiby 3. - Otherwise, parse the single digit at
s.charAt(i), convert it to a character, append it to the result, and decrementiby 1. - After the loop, reverse the
StringBuilder. - Convert the reversed
StringBuilderto a string and return it.
Walkthrough
This approach processes the string s from its end towards the beginning. We use a pointer i initialized to s.length() - 1.
When the character at s[i] is '#', we know it's the marker for a two-digit number. The number is formed by the characters at i-2 and i-1. We parse this number, find the corresponding character, and append it to our StringBuilder. We then move the pointer i back by 3 positions.
If the character at s[i] is a digit, it represents a single-digit number. We parse it, find the character, append it to the StringBuilder, and move the pointer i back by 1.
Since we are processing from right to left and appending to the StringBuilder, the resulting string will be in reverse order. Therefore, the final step is to reverse the StringBuilder before converting it to a string.
class Solution { public String freqAlphabets(String s) { StringBuilder result = new StringBuilder(); int i = s.length() - 1; while (i >= 0) { if (s.charAt(i) == '#') { // Two-digit number int num = Integer.parseInt(s.substring(i - 2, i)); result.append((char) ('a' + num - 1)); i -= 3; } else { // Single-digit number int num = s.charAt(i) - '0'; result.append((char) ('a' + num - 1)); i -= 1; } } return result.reverse().toString(); }}Complexity
Time
O(N), where N is the length of the input string `s`. The traversal is O(N), and reversing the `StringBuilder` is also O(N), leading to a total linear time complexity.
Space
O(N) to store the result in a `StringBuilder`. The space is proportional to the length of the input string, where N is the length of `s`.
Trade-offs
Pros
More elegant and less error-prone as it avoids lookahead logic.
The logic at each step is simpler: the character at the current pointer dictates the action.
Highly efficient with linear time and space complexity.
Cons
Requires a final step to reverse the constructed string, which might be slightly less intuitive than building the string in the correct order from the start.
Solutions
Solution
class Solution {public String freqAlphabets(String s) { int i = 0, n = s.length(); StringBuilder res = new StringBuilder(); while (i < n) { if (i + 2 < n && s.charAt(i + 2) == '#') { res.append(get(s.substring(i, i + 2))); i += 3; } else { res.append(get(s.substring(i, i + 1))); i += 1; } } return res.toString(); }private char get(String s) { return (char)('a' + Integer.parseInt(s) - 1); }}class Solution { public: string freqAlphabets ( string s ) { string ans = "" ; int i = 0 , n = s . size (); while ( i < n ) { if ( i + 2 < n && s [ i + 2 ] == '#' ) { ans += char ( stoi ( s . substr ( i , 2 )) + 'a' - 1 ); i += 3 ; } else { ans += char ( s [ i ] - '0' + 'a' - 1 ); i += 1 ; } } return ans ; } };class Solution: def freqAlphabets(self, s: str) -> str: def get(s): return chr(ord('a') + int(s) - 1) i, n = 0, len(s) res = [] while i < n: if i + 2 < n and s[i + 2] == '#': res . append(get(s[i: i + 2])) i += 3 else: res . append(get(s[i])) i += 1 return '' . join(res)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.