Katkat
Back

Find shortest unique substring per word

AffirmSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate string data structures (like Tries or Suffix Trees) to efficiently identify the shortest, lexicographically smallest substring that is unique to a given word within a provided collection.

Problem Statement

Given a list of words, your task is to find the shortest unique substring for each word in the list. A substring is considered 'unique' to a specific word if it does not appear as a substring in any other word in the input list.

If there are multiple substrings of the same minimum length that are unique to a word, choose the one that appears at the earliest starting index. If there is still a tie, choose the lexicographically smallest substring.

Implement the function: def find_shortest_unique_substrings(words: List[str]) -> List[str]:

Examples

Example 1: Input: ['apple', 'apply', 'ape'] Output: ['le', 'ly', 'p'] Explanation: 'le' is the shortest unique for 'apple', 'ly' for 'apply', and 'p' for 'ape'.

Example 2: Input: ['abc', 'abd'] Output: ['abc', 'abd'] Explanation: Since these are only 3 letters long and share prefixes, the full words are the shortest unique substrings.

Constraints

  • The number of words is between 1 and 1000.
  • The total number of characters across all words does not exceed 10,000.
  • All strings consist of lowercase English letters.

Edge Cases

  • Words that are substrings of other words in the list.
  • Identical words (if the input contains duplicates, treat them as the same set; a string appearing in multiple words is not unique to any of them).

Hints

Hint 1

Consider building a frequency map or a Generalized Suffix Tree for all substrings present in the input list.

Hint 2

For each word, iterate through all possible substrings starting from length 1 up to the length of the word to find the first one with a count of exactly 1 in your global map.

Hint 3

Ensure your substring extraction and global counting logic accounts for the tie-breaking rules (index first, then lexicographical order) explicitly during the search phase.

Follow-up questions

  • How would your approach change if the number of words was in the millions, but the average length of each word was very small?
  • Can you optimize the memory usage if the total number of characters is extremely large?
  • How would you modify your solution to find the shortest unique substring that appears in at least two words but not in any others?