Problem Description

You are given a string s that contains only digits ('1' to '9') and the character '#'. Your task is to decode this string into English lowercase letters using the following mapping rules:

• Single digits '1' through '9' map to letters 'a' through 'i' respectively

  • '1' → 'a'
  • '2' → 'b'
  • '3' → 'c'
  • ... and so on until '9' → 'i'

• Two-digit numbers followed by '#' (from '10#' to '26#') map to letters 'j' through 'z' respectively

  • '10#' → 'j'
  • '11#' → 'k'
  • '12#' → 'l'
  • ... and so on until '26#' → 'z'

The solution traverses the string from left to right. At each position, it checks if there's a '#' character two positions ahead. If there is, it treats the current and next digit as a two-digit number (representing letters 'j' to 'z'), processes them together, and moves forward by 3 positions. If there's no '#' ahead, it treats the current digit as a single-digit number (representing letters 'a' to 'i') and moves forward by 1 position.

For example:

• Input: "1326#" would be decoded as "acz" (where '1' → 'a', '3' → 'c', and '26#' → 'z')
• Input: "25#" would be decoded as "y" (where '25#' → 'y')

The problem guarantees that the input will always have a valid unique mapping, meaning the string can be unambiguously decoded into letters.

Intuition

The key insight is recognizing that we need to parse the string from left to right, but we must look ahead to determine how to interpret each digit. The presence of '#' acts as a delimiter that changes the meaning of the preceding digits.

When we encounter digits in the string, we face a decision: should we treat them as a single-digit mapping ('1' to '9' → 'a' to 'i') or as part of a two-digit mapping ('10#' to '26#' → 'j' to 'z')? The '#' symbol is the critical indicator - it only appears after two-digit numbers.

This leads us to a greedy approach: at each position, we first check if there's a '#' two positions ahead. If there is, we know the current and next digits form a two-digit number, so we process them together. If not, the current digit stands alone.

Why does this greedy strategy work? Because the problem guarantees a unique valid mapping. There's no ambiguity - if we see '#' at position i+2, then positions i and i+1 must form a two-digit number. We can't have a situation where we need to "backtrack" and reconsider our decisions.

The conversion itself is straightforward once we know which digits to group together. For a number n representing a letter:

• We calculate the character as chr(n + ord('a') - 1)
• The -1 offset is because 'a' corresponds to 1 (not 0), 'b' to 2, and so on

This approach processes each character exactly once, making it efficient and clean.

Solution Approach

The implementation uses a simple simulation approach with a single pass through the string. Here's how the algorithm works step by step:

Initialize Variables:

• Create an empty list ans to store the decoded characters
• Set two pointers: i = 0 (current position) and n = len(s) (string length)

Main Loop - Traverse the String:

While i < n, we perform the following checks at each position:

1. Check for Two-Digit Pattern:

   • First verify if i + 2 < n (ensuring we don't go out of bounds)
   • Then check if s[i + 2] == '#'
   • If both conditions are true, we have a two-digit number followed by '#'

2. Process Two-Digit Number (letters j-z):

   • Extract the substring s[i : i + 2] to get the two-digit number
   • Convert it to an integer using int(s[i : i + 2])
   • Calculate the corresponding character: chr(int(s[i : i + 2]) + ord('a') - 1)
   • Append the character to ans
   • Move forward by 3 positions: i += 3 (skip the two digits and the '#')

3. Process Single-Digit Number (letters a-i):

   • If there's no '#' at position i + 2, treat the current digit as standalone
   • Convert s[i] to an integer
   • Calculate the corresponding character: chr(int(s[i]) + ord('a') - 1)
   • Append the character to ans
   • Move forward by 1 position: i += 1

Character Conversion Formula:

The formula chr(num + ord('a') - 1) works because:

• ord('a') gives us the ASCII value of 'a'
• We subtract 1 because the mapping starts at 1 (not 0): '1' maps to 'a', '2' to 'b', etc.
• chr() converts the resulting ASCII value back to a character

Final Step:

After processing all characters, join the list ans into a string using ''.join(ans) and return it.

Time and Space Complexity:

• Time: O(n) where n is the length of the input string - we visit each character once
• Space: O(n) for storing the result array

Example Walkthrough

Let's walk through the decoding process with the input string "12#321".

Initial Setup:

• Input string: s = "12#321"
• Empty result list: ans = []
• Starting position: i = 0
• String length: n = 6

Step 1: Position i = 0

• Current character: '1'
• Check if i + 2 < n: 0 + 2 < 6 ✓
• Check if s[i + 2] == '#': s[2] = '#' ✓
• We found a two-digit pattern! Extract s[0:2] = "12"
• Convert: int("12") = 12
• Calculate character: chr(12 + ord('a') - 1) = chr(12 + 97 - 1) = chr(108) = 'l'
• Append 'l' to result: ans = ['l']
• Move forward by 3: i = 3

Step 2: Position i = 3

• Current character: '3'
• Check if i + 2 < n: 3 + 2 < 6 ✓
• Check if s[i + 2] == '#': s[5] = '1' ✗
• No '#' found, treat as single digit
• Convert: int('3') = 3
• Calculate character: chr(3 + ord('a') - 1) = chr(3 + 97 - 1) = chr(99) = 'c'
• Append 'c' to result: ans = ['l', 'c']
• Move forward by 1: i = 4

Step 3: Position i = 4

• Current character: '2'
• Check if i + 2 < n: 4 + 2 < 6 ✗ (would be equal to 6, not less than)
• Can't look ahead for '#', treat as single digit
• Convert: int('2') = 2
• Calculate character: chr(2 + ord('a') - 1) = chr(2 + 97 - 1) = chr(98) = 'b'
• Append 'b' to result: ans = ['l', 'c', 'b']
• Move forward by 1: i = 5

Step 4: Position i = 5

• Current character: '1'
• Check if i + 2 < n: 5 + 2 < 6 ✗
• Can't look ahead for '#', treat as single digit
• Convert: int('1') = 1
• Calculate character: chr(1 + ord('a') - 1) = chr(1 + 97 - 1) = chr(97) = 'a'
• Append 'a' to result: ans = ['l', 'c', 'b', 'a']
• Move forward by 1: i = 6

Final Step:

• i = 6 is not less than n = 6, so exit the loop
• Join the result: ''.join(['l', 'c', 'b', 'a']) = "lcba"
• Return: "lcba"

The string "12#321" successfully decodes to "lcba" where:

• "12#" → 'l' (12th letter)
• "3" → 'c' (3rd letter)
• "2" → 'b' (2nd letter)
• "1" → 'a' (1st letter)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the string s exactly once using a while loop. In each iteration, the pointer i advances by either 1 or 3 positions. Regardless of the step size, each character in the string is visited at most once. The operations inside the loop (checking conditions, string slicing s[i:i+2], character conversion with chr() and ord(), and appending to the list) all take constant time O(1). Therefore, the overall time complexity is O(n), where n is the length of the string s.

Space Complexity: O(n)

The algorithm uses an additional list ans to store the decoded characters. In the worst case, when all mappings are single-digit (like "123456789"), the output will have n characters, requiring O(n) space. The final "".join(ans) operation creates a new string which also takes O(n) space. The other variables (i, n) use constant space O(1). Therefore, the overall space complexity is O(n), where n is the length of the string s.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Out of Bounds When Checking for '#'

One of the most common mistakes is incorrectly checking for the '#' character without proper boundary validation. Developers often write:

Incorrect Code:

if s[i + 2] == '#':  # Dangerous! Can cause IndexError
    # process two-digit number

The Problem: When i is at positions n-2 or n-1 (where n = len(s)), accessing s[i + 2] will raise an IndexError. This happens because we're trying to look ahead in the string without first verifying that those positions exist.

Correct Solution:

if i + 2 < len(s) and s[i + 2] == '#':  # Safe boundary check first
    # process two-digit number

Always check the boundary condition (i + 2 < len(s)) before attempting to access s[i + 2]. Python evaluates conditions from left to right and short-circuits, so if i + 2 >= len(s), it won't even attempt to access s[i + 2].

2. Incorrect Character Conversion Formula

Another frequent error involves the mathematical conversion from numbers to characters:

Incorrect Formulas:

# Wrong: Forgetting to subtract 1
letter = chr(int(s[i]) + ord('a'))  # '1' would map to 'b' instead of 'a'

# Wrong: Using wrong base character
letter = chr(int(s[i]) + ord('A') - 1)  # Would give uppercase letters

# Wrong: Direct ASCII addition without ord()
letter = chr(int(s[i]) + 97 - 1)  # Works but not readable/maintainable

The Problem:

• The mapping starts at 1 (not 0), so '1' should map to 'a'. Without subtracting 1, '1' would incorrectly map to 'b'.
• Using ord('A') would produce uppercase letters instead of lowercase.
• Using magic numbers like 97 (ASCII value of 'a') makes code less readable.

Correct Solution:

letter = chr(int(num_str) + ord('a') - 1)

This formula correctly handles the 1-based indexing of the mapping.

3. Incorrect Index Advancement

Developers sometimes advance the index incorrectly after processing characters:

Incorrect Code:

if i + 2 < len(s) and s[i + 2] == '#':
    # process two-digit number
    i += 2  # Wrong! Only moves past the digits, not the '#'
else:
    # process single digit
    i += 1

The Problem: When processing a two-digit pattern like "10#", we need to skip all three characters (two digits plus the '#'). Moving only 2 positions would cause the '#' to be processed as if it were a digit in the next iteration.

Correct Solution:

if i + 2 < len(s) and s[i + 2] == '#':
    # process two-digit number
    i += 3  # Correctly skip both digits and the '#'
else:
    # process single digit
    i += 1

4. String Slicing Errors

When extracting the two-digit number, incorrect slicing is a common issue:

Incorrect Code:

two_digit_num = int(s[i] + s[i + 1])  # Works but less efficient
two_digit_num = int(s[i:i + 1])  # Wrong! Only gets one character
two_digit_num = int(s[i:i + 3])  # Wrong! Includes the '#'

The Problem:

• String concatenation creates unnecessary temporary strings.
• Incorrect slice boundaries either miss characters or include the '#'.

Correct Solution:

two_digit_num = int(s[i:i + 2])  # Cleanly extracts exactly two digits

Remember that Python slicing is exclusive of the end index, so s[i:i + 2] gets characters at positions i and i + 1.