Memory issues with Find Strings Problem on InterviewStreet

Question

Here is the code I wrote for the problem at http://www.interviewstreet.com/recruit/challenges/solve/view/4e1491425cf10/4efa210eb70ac where we need to to print the substring at a particular index from the lexicographicaly-sorted union of sets of substrings of the given set of strings...

import itertools
N = int(raw_input())
S = set()
for n in xrange(N):
    W = raw_input()
    L = len(W)
    for l in xrange(1,L+1):
        S=S.union(set(itertools.combinations(W, l)))
        print set(itertools.combinations(W, l))
print S
M = int(raw_input())
S = sorted(list(S))
print S
for m in xrange(M):
    Q = int(raw_input())
    try:
        print "".join(S[Q-1])
    except:
        print "INVALID"

but it gives me a Memory Error meaning that my code takes up more than 256Mb during execution.

I think the culprit is S=S.union(set(itertools.combinations(W, l))), but can't really think of a more efficient method for harvesting a unique set of substrings from the given set of strings...

Can you suggest an optimal alternative?

Answer 1

To successfully pass all test cases you need to implement something more sophisticated like suffix tree. That will allow you to solve this task in O(n) time using O(n) space.