PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Harsh Shah
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Trie, Strings
PROBLEM:
You are asked to maintain a collection of strings. Strings are added and removed from the collection. You have to find if there exists a group of k strings such that they have a common suffix of length l.
EXPLANATION:
The collection of strings can be maintained effectively in a Trie. Since the queries are about the suffix of the strings, the strings need to be processed in reverse order. Here onwards, I will assume that all the strings have been reversed just after taking their input.
The addition and removal operation can hence be performed in O(string length). As we know, that all the strings having same prefix converge at the same node in a Trie, we can keep a prefix counter in every node of the Trie denoting the number of strings having the same prefix (suffix in our case, as we have reversed the strings). Hence, if there exists a node in Trie at dpeth L having prefix counter >=K the answer to the query is Yes else the answer it No.
To answer the queries efficiently, we can maintain a data structure, an array of maps for instance. Such that M[L][K] maintains the count of number of nodes at depth L having prefix counter K. This data structure is updated each time the prefix counters of Trie change on Add and Remove queries. Since, in any map K can range from 1 to N (the number of strings having upper bound |S|), the updation can be done in O(log(|S|). This updation occurs on every addition and removal operation. Thus the complexity of maintaining the data structure is O(|S|log(|S|)) . The queries can be answer by just looking up the values in the map. Hence all queries can are answered in O(Qlog(|S|)).
Total complexity: O((Q+|S|)log(|S|))
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here