Short Encoding of Words

medium

Minimize encoded length by merging shared suffixes in a trie

Short Encoding of Words

Key Insight

A word that is a suffix of another adds no new nodes in reversed trie, so it contributes 0 length.

Step 1Insert Reversed Words
Array
time
0
me
1
bell
2
HashMap
time:4
me:2
bell:4

time, me, bell become reversed words for suffix checking.

1 / 3

Learn the Pattern

Hash MapUse a hash map for O(1) lookup to track seen elements, frequencies, or complement values during array traversal.
Practice the Code

Step-by-Step Walkthrough: Short Encoding of Words

A word that is a suffix of another adds no new nodes in reversed trie, so it contributes 0 length.

  1. Insert Reversed Words

    time, me, bell become reversed words for suffix checking.

  2. Add New Nodes for time

    time adds full path, so it contributes length+1 (5).

  3. Skip Existing Suffix Nodes

    me is already present as suffix of time, so it adds no extra nodes.