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.
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); }}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.