PROBLEM LINK:
Author: Jingbo Shang
Tester: Xiaoxu Guo
Editorialist: Pushkar Mishra
DIFFICULTY:
Easy
PREREQUISITES:
Strings, In-built data structures, Hashmaps
PROBLEM:
Given N words, find the longest such word which is common to all of them.
EXPLANATION:
The first things to note are that the length of all the words is \leq 20 and there can be a maximum of 10 words. Let the longest word in the given set of words be of length L. Thus, the total number of distinct substrings we can get from this word is \mathcal{O}(L^2). Accordingly, the total number of distinct substrings that we can get from the set of words is \mathcal{O}(NL^2).
Once, we have a list of all the distinct substrings, we just need, for each word, the number of words which it appears in. If it appears in all the N words, then it can be a potential candidate for our answer.
How do we implement this? We can use an in-built implementation of hashmap that is available in the language you are using. The hashmap will be organised as map< key,\, list> . The keys here are the distinct substrings from the given set of strings. For each key, we store a list of indices of words which it appears in. We can build this structure by taking one word at a time (say the i^{th} word) examining each its substrings, and putting inserting i in the list associated with the substrings in our map. The word can contain a same substring twice. For example, anan contains an twice. Thus, we have to make sure that we dont insert i twice into the list of a substring which appears twice in it.
Here is the pseudocode:
func get_stem(words [])
{
for (i = 1 to N in words)
{
for (all substrings `subs' of words[i])
{
if(map[subs].insert doesn't contain i)
map[subs].insert(i);
}
}
for(all keys `k' in the map)
if(k = longest and lexicographically smallest word with associated list of size = N)
return k;
}
COMPLEXITY:
\mathcal{O}(NL^3\log (NL^2)) per test case.