LeetCode 1309 - Decrypt String from Alphabet to Integer Mapping

The problem gives us a string containing digits and the '' character. This string encodes lowercase English letters usin

leetcodeeasystring

LeetCode Problem 1309

Difficulty: šŸŸ¢ Easy
Topics: String

Solution

Problem Understanding

The problem gives us a string containing digits and the '#' character. This string encodes lowercase English letters using a special mapping rule.

The mapping works in two different ways:

  • Digits '1' through '9' represent the letters 'a' through 'i'
  • Two digit numbers followed by '#', from "10#" through "26#", represent the letters 'j' through 'z'

Our task is to decode the entire string and return the corresponding plaintext string.

For example, the encoded string "10#11#12" should become:

  • "10#" ā†’ 'j'
  • "11#" ā†’ 'k'
  • "1" ā†’ 'a'
  • "2" ā†’ 'b'

So the final answer is "jkab".

The important observation is that the encoding is uniquely decodable. The problem guarantees that every input string is valid and has exactly one interpretation. This means we never need to guess between multiple decoding possibilities.

The input length can be as large as 1000 characters, which is relatively small. Even an inefficient solution would likely pass, but we should still aim for a clean linear time solution.

A naive implementation can easily make mistakes around parsing "10#" through "26#". Since both single digit and two digit forms exist, we must carefully distinguish between:

  • "1" meaning 'a'
  • "10#" meaning 'j'

The '#' character is the key signal that the previous two digits should be treated together as a single number.

Some important edge cases include:

  • Strings containing only single digit mappings
  • Strings containing only '#' based mappings
  • Mixed encodings where both forms appear together
  • Consecutive '#' patterns
  • Inputs near the maximum length

Because the input is guaranteed valid, we do not need to handle malformed cases like "27#" or stray '#' characters.

Approaches

Brute Force Approach

A brute force solution would try to reconstruct the decoded string by repeatedly examining every possible substring and checking whether it forms a valid encoding.

At each position, we could attempt:

  • A one digit decode
  • A three character decode ending with '#'

This approach works because every valid encoding corresponds to one of these two formats.

However, a truly brute force recursive implementation might repeatedly recompute overlapping subproblems. For example, when decoding from position i, we may repeatedly decode the same suffix many times.

Although the input size is small enough that even this could pass with memoization, it introduces unnecessary complexity for a problem that has a straightforward linear parsing strategy.

Optimal Approach

The key insight is that every multi digit encoding always ends with '#'.

This means we can process the string from left to right or right to left while identifying whether the current segment is:

  • A single digit mapping
  • A two digit mapping followed by '#'

A particularly clean strategy is to scan from right to left.

Why does this help?

When scanning backward:

  • If we encounter '#', we immediately know the previous two digits belong together
  • Otherwise, the current digit represents a standalone character

This completely removes ambiguity and allows us to decode the string in a single pass.

Approach Time Complexity Space Complexity Notes
Brute Force O(nĀ²) O(n) Repeatedly explores decoding possibilities
Optimal O(n) O(n) Single pass parsing using the '#' marker

Algorithm Walkthrough

  1. Initialize an empty list to store decoded characters.

We use a list because repeatedly appending characters is efficient. At the end, we can join the list into a string. 2. Start scanning the string from the end toward the beginning.

Processing backward makes the parsing logic simpler because every '#' directly tells us that the previous two digits belong together. 3. At each position, check whether the current character is '#'.

If it is, then:

  • Read the previous two digits
  • Convert them into an integer
  • Map the integer to its corresponding character
  • Move the pointer backward by 3 positions total
  1. If the current character is not '#', treat it as a single digit mapping.

Convert the digit into an integer and map it to its corresponding lowercase letter. 5. Append each decoded character to the result list.

Since we are scanning backward, characters are collected in reverse order. 6. Reverse the result list at the end.

This restores the original left to right order of the decoded string. 7. Join the characters into a final string and return it.

Why it works

The algorithm works because the encoding format is unambiguous.

Every two digit mapping must end with '#', so whenever we encounter '#', we know exactly how to interpret the previous two digits. Any digit not associated with '#' must represent a single digit mapping.

By processing the string from right to left, we always know whether to consume one character or three characters. This guarantees that every encoded segment is decoded correctly exactly once.

Python Solution

class Solution:
    def freqAlphabets(self, s: str) -> str:
        decoded_chars = []
        index = len(s) - 1

        while index >= 0:
            if s[index] == '#':
                number = int(s[index - 2:index])
                decoded_chars.append(chr(ord('a') + number - 1))
                index -= 3
            else:
                number = int(s[index])
                decoded_chars.append(chr(ord('a') + number - 1))
                index -= 1

        return ''.join(reversed(decoded_chars))

The implementation follows the exact logic from the algorithm walkthrough.

We begin by creating an empty list called decoded_chars. This stores the decoded letters as we process the string.

The variable index starts at the end of the string. We move backward through the input because this makes handling '#' patterns straightforward.

Inside the loop, we check whether the current character is '#'.

If it is, we extract the previous two digits using slicing:

s[index - 2:index]

This gives us the two digit number corresponding to letters 'j' through 'z'.

We convert the numeric value into a character using:

chr(ord('a') + number - 1)

This shifts from the ASCII value of 'a' to the desired character.

If the current character is not '#', then it must be a single digit mapping. We decode it directly using the same character conversion formula.

Because characters are appended while scanning backward, the decoded list is reversed at the end before joining into the final string.

Go Solution

func freqAlphabets(s string) string {
    decoded := make([]byte, 0)
    index := len(s) - 1

    for index >= 0 {
        if s[index] == '#' {
            number := int(s[index-2]-'0')*10 + int(s[index-1]-'0')
            decoded = append(decoded, byte('a'+number-1))
            index -= 3
        } else {
            number := int(s[index] - '0')
            decoded = append(decoded, byte('a'+number-1))
            index--
        }
    }

    // Reverse the result
    for left, right := 0, len(decoded)-1; left < right; left, right = left+1, right-1 {
        decoded[left], decoded[right] = decoded[right], decoded[left]
    }

    return string(decoded)
}

The Go implementation follows the same overall strategy as the Python version.

One notable difference is that Go strings are byte based, so we use a []byte slice to efficiently build the result.

Instead of substring parsing with int(), we manually compute two digit numbers using character arithmetic:

int(s[index-2]-'0')*10 + int(s[index-1]-'0')

Since the decoded characters are appended in reverse order, we manually reverse the byte slice before converting it back into a string.

There are no integer overflow concerns because the largest possible value is only 26.

Worked Examples

Example 1

Input:

s = "10#11#12"
Step Index Current Character Action Decoded Characters
1 7 2 Single digit, decode 2 ā†’ b ['b']
2 6 1 Single digit, decode 1 ā†’ a ['b', 'a']
3 5 # Decode 11# ā†’ k ['b', 'a', 'k']
4 2 # Decode 10# ā†’ j ['b', 'a', 'k', 'j']

The characters were collected in reverse order.

After reversing:

['j', 'k', 'a', 'b']

Final answer:

"jkab"

Example 2

Input:

s = "1326#"
Step Index Current Character Action Decoded Characters
1 4 # Decode 26# ā†’ z ['z']
2 1 3 Decode 3 ā†’ c ['z', 'c']
3 0 1 Decode 1 ā†’ a ['z', 'c', 'a']

After reversing:

['a', 'c', 'z']

Final answer:

"acz"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed at most once
Space O(n) The output list stores the decoded string

The algorithm performs a single linear scan through the input string. Every step consumes either one character or three characters, but no character is revisited.

The auxiliary space comes from storing the decoded result. Since the output itself can contain up to n characters, the space complexity is linear.

Test Cases

solution = Solution()

assert solution.freqAlphabets("10#11#12") == "jkab"  # mixed single and double digit mappings
assert solution.freqAlphabets("1326#") == "acz"  # ending with # mapping
assert solution.freqAlphabets("1") == "a"  # smallest possible input
assert solution.freqAlphabets("9") == "i"  # highest single digit mapping
assert solution.freqAlphabets("10#") == "j"  # smallest # mapping
assert solution.freqAlphabets("26#") == "z"  # largest # mapping
assert solution.freqAlphabets("123456789") == "abcdefghi"  # only single digit mappings
assert solution.freqAlphabets("10#11#12#13#") == "jklm"  # consecutive # mappings
assert solution.freqAlphabets("25#24#123") == "yxabc"  # mixed ordering
assert solution.freqAlphabets("20#5") == "te"  # # mapping followed by single digit
Test Why
"10#11#12" Validates mixed encoding formats
"1326#" Validates decoding ending with '#'
"1" Smallest valid input
"9" Highest single digit mapping
"10#" Smallest two digit mapping
"26#" Largest two digit mapping
"123456789" All single digit encodings
"10#11#12#13#" Consecutive '#' encodings
"25#24#123" Mixed decoding order
"20#5" Combination of multi digit and single digit mappings

Edge Cases

One important edge case is when the input contains only single digit mappings, such as "123456789". A buggy implementation might incorrectly attempt to group digits together even without a trailing '#'. This implementation avoids that problem by only treating numbers as two digit encodings when a '#' is explicitly present.

Another important case is consecutive '#' encodings, such as "10#11#12#". A forward parsing implementation can accidentally skip characters or misalign indices when consuming three character groups. By scanning backward, this implementation always knows exactly when to consume three characters, which prevents index handling bugs.

A third edge case is the minimum input size, such as "1". Some implementations may incorrectly assume that there are always at least three characters available before checking for '#'. This solution safely handles single character inputs because it only accesses index - 2 when the current character is actually '#', and the problem guarantees valid formatting.