Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

**Problem:** Sphere Online Judge (SPOJ) – Problem CPRMT

**Solution:** That’s short and nice problem. You have to find all letters which are in both strings. I’d actually like to see some other implementations of this. I bet there are some languages which handle this in a smart way.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
def intersection(lst1, lst2): same = [] if len(lst1) > len(lst2): for k in lst1: try: # checks if element k is in lst2 lst2.remove(k) same.append(k) except: pass else: for k in lst2: try: lst1.remove(k) same.append(k) except: pass same.sort() return same while True: try: inp1 = raw_input() inp2 = raw_input() common = intersection(list(inp1), list(inp2)) print "".join(common) except: break |