Frontend School

Distinguishing Prefix Sum

DSA
hard

Distinguishing Prefix Sum

Hard
Trie
String
Data Structures
Algorithms

Overview

In modern search and auto-completion systems, efficiently identifying and distinguishing between a vast number of terms is crucial. This problem challenges you to optimize dictionary storage by calculating a unique "distinguishing prefix sum." You'll build a specialized Trie to determine the shortest prefix for each word that makes it unique within the dictionary, with a specific rule for words that are prefixes of others. This metric helps evaluate the inherent prefix uniqueness and potential for compression in a given set of words.

What you need to do / Task

Implement the function distinguishingPrefixSum that takes an array of strings (words) and calculates the sum of their distinguishing prefix lengths based on the following rules:

  1. For each word W in the input list, find its distinguishing prefix.
  2. A distinguishing prefix for W is defined as the shortest prefix P of W such that P is not a prefix of any other word W' in the dictionary (W' != W).
  3. Special Rule: If W itself is a prefix of another word W' in the dictionary, then its distinguishing prefix is considered to be its full length, length(W).
  4. Return the total sum of these distinguishing prefix lengths for all words.

Input & output

  • Input: words: string[] - An array of unique non-empty strings, representing the dictionary.
  • Output: number - The total sum of distinguishing prefix lengths for all words.

Clarifications

  • Empty input: The input words array will not be empty.
  • Duplicate words: All words in the input array are guaranteed to be unique.
  • Word characters: Words consist only of lowercase English letters ('a'-'z'.)

Examples

1

Example 1

Input:

words = ["apple", "apply", "apricot", "banana"]

Output:

14

Note:

  • "apple": Not a prefix of any other word. Shortest unique prefix is "apple" (length 5).
  • "apply": Not a prefix of any other word. Shortest unique prefix is "apply" (length 5).
  • "apricot": Not a prefix of any other word. Shortest unique prefix is "apr" (length 3). ('a' and 'ap' are shared with "apple", "apply", but 'apr' is unique to "apricot").
  • "banana": Not a prefix of any other word. Shortest unique prefix is "b" (length 1). ('b' is not shared with any other word). Total sum = 5 + 5 + 3 + 1 = 14.
2

Example 2

Input:

words = ["app", "apple"]

Output:

7

Note:

  • "app": Is a prefix of "apple". According to the special rule, its distinguishing prefix is its full length, "app" (length 3).
  • "apple": Not a prefix of any other word. Shortest unique prefix is "appl" (length 4). ('a', 'ap', 'app' are shared with "app", but 'appl' is unique to "apple"). Total sum = 3 + 4 = 7.
3

Example 3

Input:

words = ["cat", "cow", "dog"]

Output:

5

Note:

  • "cat": Not a prefix of any other word. 'c' is shared with "cow". 'ca' is the shortest prefix that is not a prefix of "cow" or "dog". Length 2.
  • "cow": Not a prefix of any other word. 'c' is shared with "cat". 'co' is the shortest prefix that is not a prefix of "cat" or "dog". Length 2.
  • "dog": Not a prefix of any other word. 'd' is the shortest prefix that is not a prefix of "cat" or "cow". Length 1. Total sum = 2 + 2 + 1 = 5.

Constraints

Constraints & assumptions

  • 1 <= words.length <= 10^5
  • 1 <= words[i].length <= 20
  • 1 <= sum(words[i].length) <= 10^6 (Total length of all words)
  • Words contain only lowercase English letters.

What interviewers evaluate

  • Trie Implementation: Correct and efficient construction of the Trie data structure, including appropriate node properties.
  • Algorithmic Correctness: Accurate application of the distinguishing prefix logic, correctly handling both standard uniqueness and the special prefix rule.
  • Time and Space Complexity: Optimal solution achieving O(L) time and space complexity, where L is the total length of all words.
  • Code Quality: Clean, readable, and well-structured code with appropriate variable names and comments where necessary.

Loading editor...