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?
>>> 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). – Paul Martel Jan 19 '12 at 4:28