Short Encoding of Words - Practice Coding Problems

Short Encoding of Words - Problem

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 s ends with the '#' character
For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i]

Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

Input & Output

Example 1 — Basic Suffix Removal

$ Input: words = ["time", "me", "bell"]

› Output: 10

💡 Note: The word "me" is a suffix of "time", so we can encode it as part of "time". The encoding becomes "time#bell#" with length 10.

Example 2 — No Suffixes

$ Input: words = ["t"]

› Output: 2

💡 Note: Only one word, so the encoding is "t#" with length 2.

Example 3 — Multiple Suffix Relationships

$ Input: words = ["time", "me", "e"]

› Output: 5

💡 Note: Both "me" and "e" are suffixes of "time", so we only need to encode "time" as "time#" with length 5.

Constraints

1 ≤ words.length ≤ 2000
1 ≤ words[i].length ≤ 7
words[i] consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words: ["time", "me", "bell"]

Process

Identify "me" as suffix of "time", remove it

Output

Encoding length: "time#bell#" = 10

Key Takeaway

🎯 Key Insight: Words that are suffixes of other words can be omitted from the encoding

Asked in

G Google 15 M Microsoft 8

The key insight is that if word A is a suffix of word B, we don't need to encode A separately since it can be reconstructed from B's encoding. The optimal approach uses a trie built from reversed words to efficiently identify suffix relationships. Time: O(n×m), Space: O(n×m).

Common Approaches

Approach	Time	Space	Notes
✓ Trie-Based Solution	O(n×m)	O(n×m)	Build a reverse trie to efficiently find suffix relationships
Hash Set Optimization	O(n×m²)	O(n×m)	Use hash set to quickly check if words are suffixes of others
Brute Force - Check All Suffixes	O(n²×m)	O(1)	For each word, check if it's a suffix of any other word

Trie-Based Solution — Algorithm Steps

Step 1: Reverse all words and build a trie
Step 2: For each word, check if it's a prefix of another in reverse trie
Step 3: Keep only non-prefix words and calculate total length

Visualization

Tap to expand

Step-by-Step Walkthrough

Reverse Words

Build trie from reversed words

Leaf Check

Words at leaf nodes are not suffixes

Calculate

Sum lengths of leaf words plus separators

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 1000
#define MAX_LEN 101
#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool isEnd;
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)calloc(1, sizeof(TrieNode));
    return node;
}

int solution(char words[][MAX_LEN], int n) {
    // Remove duplicates first
    char uniqueWords[MAX_WORDS][MAX_LEN];
    int uniqueCount = 0;
    
    for (int i = 0; i < n; i++) {
        bool isDuplicate = false;
        for (int j = 0; j < uniqueCount; j++) {
            if (strcmp(words[i], uniqueWords[j]) == 0) {
                isDuplicate = true;
                break;
            }
        }
        if (!isDuplicate) {
            strcpy(uniqueWords[uniqueCount], words[i]);
            uniqueCount++;
        }
    }
    
    // Build trie from reversed words
    TrieNode* root = createNode();
    
    for (int i = 0; i < uniqueCount; i++) {
        TrieNode* node = root;
        int len = strlen(uniqueWords[i]);
        for (int j = len - 1; j >= 0; j--) {
            int index = uniqueWords[i][j] - 'a';
            if (!node->children[index]) {
                node->children[index] = createNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
    
    // Check which words are not suffixes of others
    int totalLength = 0;
    for (int i = 0; i < uniqueCount; i++) {
        TrieNode* node = root;
        int len = strlen(uniqueWords[i]);
        for (int j = len - 1; j >= 0; j--) {
            int index = uniqueWords[i][j] - 'a';
            node = node->children[index];
        }
        
        // Check if this node has no children
        bool hasChildren = false;
        for (int k = 0; k < ALPHABET_SIZE; k++) {
            if (node->children[k]) {
                hasChildren = true;
                break;
            }
        }
        
        if (!hasChildren) {
            totalLength += len + 1;
        }
    }
    
    return totalLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array manually
    char words[MAX_WORDS][MAX_LEN];
    int count = 0;
    
    char* token = strtok(line + 1, ","); // Skip opening [
    while (token != NULL && count < MAX_WORDS) {
        // Remove quotes and spaces
        while (*token == ' ' || *token == '"') token++;
        int len = strlen(token);
        while (len > 0 && (token[len-1] == ' ' || token[len-1] == '"' || token[len-1] == ']')) {
            token[len-1] = '\0';
            len--;
        }
        strcpy(words[count], token);
        count++;
        token = strtok(NULL, ",");
    }
    
    int result = solution(words, count);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Build trie takes O(n×m) time, checking each word takes O(m) time

✓ Linear Growth

Space Complexity

O(n×m)

Trie stores all characters from all words, up to n×m total characters

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Trie-Based Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler