BackhardTrie

Optimized Prefix Repository Solution

Problem Statement

Design a data structure to store and manage a collection of strings, supporting two primary operations: adding a string to the repository and retrieving the lexicographically smallest prefix of a given length that exists in the repository. If no such prefix exists for the specified length, the retrieval operation should return an empty string.

Example 1
Input
add('abce'), add('abcd'), getMinPrefix(3)
Output
undefined

Explanation: Both 'abce' and 'abcd' have a common prefix 'abc' of length 3, and 'abc' is lexicographically the smallest among all possible prefixes of length 3 in the repository.

Example 2
Input
add('xyz'), add('xy'), getMinPrefix(2)
Output
undefined

Explanation: The prefix 'xy' of length 2 from the string 'xy' is the lexicographically smallest among all prefixes of length 2 in the repository.

Example 3
Input
add('pqr'), getMinPrefix(1)
Output
undefined

Explanation: The single character 'p' is the shortest prefix and is lexicographically the smallest for the given length of 1.

Constraints

  • The total number of strings added to the repository will not exceed 10^5.
  • The total length of all strings added will not exceed 10^6 characters.
  • Each retrieval operation should be performed in reasonable time complexity, e.g., O(n) or better where n is the length of the strings or the given length.
  • The repository is initially empty.

More Trie Problems

Protocol Pipeline Partition 2easyNode Payload Resolver 7easyNetwork Network Tracker 11easyProtocol Sensor Optimizer 16easy
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free