Skip to main content
Back to ChallengesHuffman CodingHard 50 min

Huffman Coding

Given a string of characters, return the Huffman encoding of the string.

Huffman coding is a lossless data compression algorithm. It assigns variable-length codes to input characters, with lengths based on the frequencies of the corresponding characters.

Examples

Input: s = 'abcdef'
Output: Custom output depending on tree shape (often tested via total encoded length). For now, return a frequency map.
Normally Huffman constructs a prefix tree.

Constraints

  • • 1 <= s.length <= 10^5

Complexity Analysis

Time
O(N log N) using a proper Min-Heap.
Space
O(U) where U is unique characters.

Test Cases

#1 a:2 bits, b:2 bits, c:1 bit. 1*2 + 2*2 + 3*1 = 9
Input: s = 'abbccc'
Expected: 9
#2 Single character
Input: s = 'a'
Expected: 1
Output
Click "Run Code" to see output here...