Problem 1309

Abstract / Summary

Transform a string of digits into letters by mapping groups of one to three digits to letters a to s using a simple number to letter conversion.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1309.py

class Solution:
    def freqAlphabets(self, s: str) -> str:
        alpha   = {}
        numeric = {}
        for i in range(26):
            code  = str(i + 1)
            ascii = chr(i + ord("a"))
            alpha[code]    = ascii
            numeric[ascii] = code
        # handle cases such as "10#"
        alpha["0"]   = "_" # placeholder
        numeric["_"] = "0"

        result = []
        for c in s:
            if c == "#":
                two = numeric[result.pop()]
                one = numeric[result.pop()]
                result.append(alpha[one + two])
            else:
                result.append(alpha[c])

        return "".join(result)
23 lines | 688 bytes | submitted December 21, 2023 | GitHub   15% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 80% (100k+ submissions).

Typical patterns to solve this problem:
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided Solution class implements a method freqAlphabets that translates an encoded string into its alphabetical representation. The encoding follows a pattern where numbers 1-9 map directly to letters a-i, while two-digit numbers 10-26 are followed by a # and map to j-z. The implementation builds bidirectional lookup tables, processes the input character by character, and reconstructs the decoded string.

Key Steps

The algorithm can be divided into three logical phases.

The first phase constructs two dictionaries: one that maps numeric codes to letters (alpha) and another that maps letters back to their numeric codes (numeric).

alpha   = {}
numeric = {}
for i in range(26):
    code  = str(i + 1)
    ascii = chr(i + ord("a"))
    alpha[code]    = ascii
    numeric[ascii] = code

A special placeholder entry is added to handle the # delimiter.

alpha["0"]   = "_"   # placeholder
numeric["_"] = "0"

The second phase iterates over the input string s. When a # is encountered, the algorithm retrieves the two preceding digits from the result stack, looks up their combined numeric code, and appends the corresponding letter. For any other character, the single-digit mapping is applied directly.

result = []
for c in s:
    if c == "#":
        two = numeric[result.pop()]
        one = numeric[result.pop()]
        result.append(alpha[one + two])
    else:
        result.append(alpha[c])

The final phase concatenates the list of characters into the output string.

return "".join(result)

Edge Cases Handled

The code explicitly accommodates the # delimiter that signals a two-digit code. By storing a placeholder ("_") in the alpha dictionary and a corresponding entry in numeric, the algorithm can safely pop the last two characters from the result list even when they represent a multi-digit number. This design prevents index errors when the input ends with a # sequence such as "10#".

Additionally, the dictionaries cover the full range of 1-26, ensuring that any valid numeric token, whether single or double digit, resolves to a defined letter. The use of string keys ("1" … "26") aligns with the character-wise iteration of the input, allowing direct lookup without additional type conversion.

Performance Optimizations

The implementation precomputes both forward and reverse lookup tables before processing the input. This eliminates repeated calculation of character codes during the main loop, guaranteeing constant-time dictionary access for each token.

The result is accumulated in a list rather than concatenating strings on each iteration. List append and pop operations are amortized O(1), and the final join produces the output in a single pass, avoiding the quadratic cost associated with repeated string concatenation.

By handling the # case through a pop-based reconstruction of the two-digit number, the algorithm avoids scanning backward or slicing the original string, which reduces overhead and keeps the processing linear with respect to the length of the input.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a secret code book filled with tiny squares. Each square has a number and a letter paired together, like a team. The numbers one through nine are friends with the alphabet letters a through i. If you want to say something bigger than nine, like ten or eleven, you put a little gate sign at the end to show that two numbers belong together as one letter.

First, the code makes a map so it knows exactly which number matches which letter. It builds this map by counting from one to twenty-six and giving each one a letter friend.

Now, imagine the code is looking at a long line of numbered beads. It picks up each bead one by one. If it sees a regular number, it quickly looks in the map, finds the matching letter, and writes that letter down in a row. But if it sees that special gate sign, it notices that the last two numbers were actually a team playing dress-up as a big letter. It takes those two numbers, combines them to find the right letter in the map, and puts that letter down instead. By the time it reaches the end of the line, all those numbers have turned back into letters to tell you a story.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 6 | μ = 5.65 | σ = 1.71

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java C Go Rust TS
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fsq C++
JoshCrozier JS
keineahnung2345 C++
Krazune C++
lkwq007 Python
suxrobGM C#
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C, C++, Go, Java, Python, Rust, TypeScript
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C++
lkwq007 Python
suxrobGM C#
varunu28 Java
YuriSpiridonov Python
32 links | 19 authors | 10 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

10 solutions   December 21, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality