×

# STEM - Editorial

Author: Jingbo Shang
Tester: Xiaoxu Guo
Editorialist: Pushkar Mishra

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.

# SAMPLE SOLUTIONS:

This question is marked "community wiki".

1.3k156581
accept rate: 4%

19.8k350498541

I am getting "Access Denied" errors when trying to view solutions. Please make the solutions public as soon as possible. Thanks!

(19 Oct '15, 00:03)

 1 skysarthak fails for the test case 1 3 ab ba b raj_ankit744 needs a step of the form if (f[0] == 0 || strcmp(ch,f)<0) strcpy(f,ch); answered 19 Oct '15, 03:44 595●1●7 accept rate: 26%
 0 Why am I getting WA ..my solution is https://www.codechef.com/viewsolution/8583271.. please help me. thanks. answered 19 Oct '15, 00:28 1 accept rate: 0%
 0 Any idea why this https://www.codechef.com/viewsolution/8579208, is giving WA? Any testcase will be helpful. Have tried out multiple testcases but haven't found any failure pattern yet. Thanks answered 19 Oct '15, 14:32 1 accept rate: 0%
 0 My approach: Pick a reference string. Ideally the shortest but assuming malevolent test cases that's not too important. Test the single characters for appearance in the other strings. repeat over increasing string lengths until finding no longer strings: where two consecutive positions succeeded in the previous round, test in the other strings for appearance of the one-longer string that they covered together. (e.g. having found asdf and sdfg, test for asdfg) Collect the set of longest strings and sort for the answer. my submission answered 18 Aug '18, 10:42 5★joffan 948●8 accept rate: 13%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,639
×3,746
×349
×53
×5
×1

question asked: 17 Oct '15, 01:12

question was seen: 4,444 times

last updated: 18 Aug '18, 10:42