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?

• Paul Martel: For starters, type this at the python prompt >>> import itertools >>> for i in itertools.combinations("ABCDE",3): ... print i. Getting just what you want? Then you may want to review your definition of substring (and/or contiguous).

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.