Return to Revisions

I was trying to solve this questions:

Given an input string, find all combination of unique substrings, which are anagrams of each other and distinct from each other. The substrings must follow 2 <= length(substring) < len(original string).

Example 1:

• String: "vadapav"
• substrings: va, vad, vada, vadap, vadapa, ad, ada, adap, adapa, adapav, da, dap, dapa, dapav, ap, apa, apav, pa, pav, av
• Output: (va, av), (ad, da), (ap, pa)

How can it be optimised in terms of algorithmic and code complexity?

# Code goes below
from collections import defaultdict
import itertools
def anagram_substring(str):
 substr_list = []
 ans = []
 is_present = defaultdict(int)
 for i in range(2,len(str)):
 substr_list.extend([''.join(substr) for substr in itertools.combinations(str, i)])
 for substr in substr_list:
 is_present[substr] +=1
 rev_substr = substr[::-1]
 if is_present[rev_substr] and rev_substr!=substr:
 ans.append([substr,rev_substr])
 return ans
str = raw_input().strip()
print anagram_substring(str)