Short Encoding of Words
MedPrompt
A valid encoding of an array of words is any reference string s and array of indices indices such that:
words.length == indices.length- The reference string
sends with the'#'character. - For each index
indices[i], the substring ofsstarting fromindices[i]and up to (but not including) the next'#'character is equal towords[i].
Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.
Example 1:
"time#bell#" and indices = [0, 2, 5Example 2:
Input: words = ["t"]
Output: 2
Explanation: A valid encoding would be s = "t#" and indices = [0].
Constraints:
1 <= words.length <= 20001 <= words[i].length <= 7words[i]consists of only lowercase letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach identifies words that are suffixes of other words and excludes them from the final count. It uses a Set to efficiently store the initial words and then iterates through each word, removing any of its suffixes that are also present in the set. The final length is the sum of the lengths of the remaining words plus a '#' for each.
Algorithm
- Create a
HashSetfrom the inputwordsarray to store unique words. - Iterate through each
wordin the originalwordsarray. - For each
word, generate all its proper suffixes (substrings starting from index 1). - For each generated
suffix, attempt to remove it from theHashSet. - After the iteration, the
HashSetwill only contain words that are not suffixes of any other word. - Calculate the final length by summing
word.length() + 1for each word remaining in the set.
Walkthrough
The core idea is that if a word w1 is a suffix of w2, we only need to encode w2. The encoding for w1 is implicitly included. For example, encoding "time#" also covers "me".
To implement this, we first add all unique words to a HashSet. This handles duplicates and allows for quick removal.
Then, we iterate through each word from the original list. For each word, we generate all its possible proper suffixes (e.g., for "time", the suffixes are "ime", "me", "e"). For each generated suffix, we attempt to remove it from our HashSet. If the suffix exists in the set, it will be removed.
After checking all words and removing their suffixes, the set will only contain words that are not suffixes of any other word in the original list. These are the words we must include in our reference string. The final length is the sum of the lengths of these remaining words, plus 1 for each '#' delimiter.
import java.util.Arrays;import java.util.HashSet;import java.util.Set; class Solution { public int minimumLengthEncoding(String[] words) { Set<String> goodWords = new HashSet<>(Arrays.asList(words)); for (String word : words) { // We only need to check for suffixes if the word itself is in the set if (goodWords.contains(word)) { for (int i = 1; i < word.length(); i++) { String suffix = word.substring(i); goodWords.remove(suffix); } } } int totalLength = 0; for (String word : goodWords) { totalLength += word.length() + 1; } return totalLength; }}Complexity
Time
O(N * K^2), where N is the number of words and K is the maximum length of a word. For each of the N words, we iterate up to K-1 times to generate suffixes. Each suffix generation (`substring`) and set removal (`remove`) takes O(K) time on average.
Space
O(N * K), where N is the number of words and K is the maximum length of a word. This space is used to store the words in the `HashSet`.
Trade-offs
Pros
Relatively simple to understand and implement.
Correctly handles duplicate words by using a set.
Cons
Inefficient due to nested loops and repeated string operations (substring creation).
The time complexity of O(N * K^2) can be too slow for larger inputs where K is not small.
This approach transforms the suffix problem into a prefix problem by reversing all words. By sorting the reversed words lexicographically, we can easily check if one word is a prefix of another in a single pass, thus identifying which words are suffixes of others.
Algorithm
- Create a
Setof words to handle duplicates. - Create a new array by reversing each unique word.
- Sort the array of reversed words lexicographically.
- Initialize
totalLength = 0. - Iterate from
i = 0ton-2. Ifreversed_words[i+1]does not start withreversed_words[i], it means the original word is not a suffix of the next, so we add its encoded length (length + 1) tototalLength. - After the loop, add the encoded length of the last word to
totalLength. - Return
totalLength.
Walkthrough
The key insight is that word1 is a suffix of word2 if and only if reverse(word1) is a prefix of reverse(word2). For example, "me" is a suffix of "time", and "em" is a prefix of "emit".
By sorting an array of the reversed words, we group words with common prefixes together. For instance, "em" and "emit" would be adjacent after sorting.
The algorithm proceeds as follows:
- First, remove duplicate words using a
Setto avoid redundant processing. - Reverse each unique word.
- Sort the array of reversed words lexicographically.
- Iterate through the sorted array. If a word
reversed_words[i]is a prefix of the next wordreversed_words[i+1], it means the original word corresponding toreversed_words[i]is a suffix of the original word forreversed_words[i+1]. Therefore, we don't need to count it. - We only add the length of a word (
word.length() + 1) to our total if it's not a prefix of the next one. The last word in the sorted list is always counted as it cannot be a prefix of any subsequent word.
import java.util.Arrays;import java.util.HashSet;import java.util.Set; class Solution { public int minimumLengthEncoding(String[] words) { Set<String> uniqueWordsSet = new HashSet<>(Arrays.asList(words)); String[] uniqueWords = new String[uniqueWordsSet.size()]; int k = 0; for (String word : uniqueWordsSet) { uniqueWords[k++] = new StringBuilder(word).reverse().toString(); } Arrays.sort(uniqueWords); int totalLength = 0; for (int i = 0; i < uniqueWords.length - 1; i++) { if (!uniqueWords[i+1].startsWith(uniqueWords[i])) { totalLength += uniqueWords[i].length() + 1; } } // Add the length of the last word, if the array is not empty if (uniqueWords.length > 0) { totalLength += uniqueWords[uniqueWords.length - 1].length() + 1; } return totalLength; }}Complexity
Time
O(N*K + K * N log N), where N is the number of unique words and K is the maximum length. This is dominated by the sorting step and simplifies to O(K * N log N).
Space
O(N * K) to store the unique words and their reversed versions.
Trade-offs
Pros
More efficient than the brute-force suffix checking, especially when K is large.
Cleverly transforms the problem into a simpler prefix check after sorting.
Cons
Requires extra space to store the reversed words.
The sorting step's performance depends on string comparison, which can be costly if K is large.
This is the most optimal approach. It uses a Trie (prefix tree) data structure to efficiently handle the prefix relationships among reversed words. By inserting all reversed words into a Trie, the words that need to be encoded correspond to the leaves of the Trie, and their combined length can be found with a single traversal.
Algorithm
- Define a
TrieNodeclass. - Create a
HashSetfrom the inputwordsto handle duplicates. - Initialize an empty Trie data structure.
- For each unique word, reverse it and insert it into the Trie.
- Perform a Depth-First Search (DFS) traversal starting from the Trie's root, keeping track of the current path depth.
- If a node is a leaf (has no children), it represents a word that is not a suffix of any other. Add its encoded length (
depth) to a total sum. The word length isdepth - 1, soword_length + 1for the '#' is simplydepth. - Return the total sum after the traversal is complete.
Walkthrough
As with the sorting approach, we convert the suffix problem to a prefix problem by reversing the words. A Trie is a perfect data structure for managing and querying prefixes.
We build a Trie and insert each reversed word into it. For example, inserting "emit" (reverse of "time") creates a path e -> m -> i -> t. When we then insert "em" (reverse of "me"), we traverse the existing path e -> m and do not create new nodes.
The key observation is that if a reversed word rw1 is a prefix of another reversed word rw2, then the path for rw1 in the Trie will be a prefix of the path for rw2. The node where rw1 ends will not be a leaf node (it will have children).
Therefore, the words that are not suffixes of any other word correspond to the reversed words that are not prefixes of any other reversed word. In the Trie, these are represented by paths ending in leaf nodes (nodes with no children). The length of the shortest encoding is the sum of (depth of leaf + 1) for every leaf node.
import java.util.Arrays;import java.util.HashSet;import java.util.Set; class Solution { class TrieNode { TrieNode[] children = new TrieNode[26]; } public int minimumLengthEncoding(String[] words) { Set<String> uniqueWords = new HashSet<>(Arrays.asList(words)); TrieNode root = new TrieNode(); // Build the Trie with reversed words for (String word : uniqueWords) { TrieNode current = root; for (int i = word.length() - 1; i >= 0; i--) { char c = word.charAt(i); if (current.children[c - 'a'] == null) { current.children[c - 'a'] = new TrieNode(); } current = current.children[c - 'a']; } } // Use DFS to find all leaf nodes and sum their path lengths int[] totalLength = {0}; dfs(root, 1, totalLength); return totalLength[0]; } private void dfs(TrieNode node, int depth, int[] totalLength) { boolean isLeaf = true; for (TrieNode child : node.children) { if (child != null) { isLeaf = false; dfs(child, depth + 1, totalLength); } } if (isLeaf && depth > 1) { // A leaf node represents a word that is not a suffix of another. // The word's length is `depth - 1`. // The encoded length is `word_length + 1` which is `(depth - 1) + 1 = depth`. totalLength[0] += depth; } }}Complexity
Time
O(N * K), where N is the number of words and K is the maximum length of a word. Each character of each word is visited once to build the Trie and once during the DFS traversal.
Space
O(N * K) in the worst case for the Trie, where each character of each word creates a new node.
Trade-offs
Pros
Most efficient time complexity at O(N * K).
Scales well with the number of words and their lengths.
Provides a clean and structured way to solve prefix/suffix problems.
Cons
More complex to implement compared to other approaches.
Requires understanding of the Trie data structure.
Solutions
Solution
class Trie { Trie [] children = new Trie [ 26 ]; } class Solution { public int minimumLengthEncoding ( String [] words ) { Trie root = new Trie (); for ( String w : words ) { Trie cur = root ; for ( int i = w . length () - 1 ; i >= 0 ; i --) { int idx = w . charAt ( i ) - 'a' ; if ( cur . children [ idx ] == null ) { cur . children [ idx ] = new Trie (); } cur = cur . children [ idx ]; } } return dfs ( root , 1 ); } private int dfs ( Trie cur , int l ) { boolean isLeaf = true ; int ans = 0 ; for ( int i = 0 ; i < 26 ; i ++) { if ( cur . children [ i ] != null ) { isLeaf = false ; ans += dfs ( cur . children [ i ], l + 1 ); } } if ( isLeaf ) { ans += l ; } return ans ; } }struct Trie { Trie * children [ 26 ] = { nullptr }; }; class Solution { public: int minimumLengthEncoding ( vector < string >& words ) { auto root = new Trie (); for ( auto & w : words ) { auto cur = root ; for ( int i = w . size () - 1 ; i >= 0 ; -- i ) { if ( cur -> children [ w [ i ] - 'a' ] == nullptr ) { cur -> children [ w [ i ] - 'a' ] = new Trie (); } cur = cur -> children [ w [ i ] - 'a' ]; } } return dfs ( root , 1 ); } private: int dfs ( Trie * cur , int l ) { bool isLeaf = true ; int ans = 0 ; for ( int i = 0 ; i < 26 ; ++ i ) { if ( cur -> children [ i ] != nullptr ) { isLeaf = false ; ans += dfs ( cur -> children [ i ], l + 1 ); } } if ( isLeaf ) { ans += l ; } return ans ; } };class Trie : def __init__ ( self ) -> None : self . children = [ None ] * 26 class Solution : def minimumLengthEncoding ( self , words : List [ str ]) -> int : root = Trie () for w in words : cur = root for i in range ( len ( w ) - 1 , - 1 , - 1 ): idx = ord ( w [ i ]) - ord ( 'a' ) if cur . children [ idx ] == None : cur . children [ idx ] = Trie () cur = cur . children [ idx ] return self . dfs ( root , 1 ) def dfs ( self , cur : Trie , l : int ) -> int : isLeaf , ans = True , 0 for i in range ( 26 ): if cur . children [ i ] != None : isLeaf = False ans += self . dfs ( cur . children [ i ], l + 1 ) if isLeaf : ans += l return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.