Anagram substrings in a string

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



• 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(list)
    for i in xrange(len(str)):
            for j in xrange(i+2, len(str)+1):
                substr_list.append(str[i:j])

        substr_list = list(set(substr_list))        
    for substr in substr_list:
        if is_present[''.join(sorted(substr))]:
                    for anagram_str in is_present[''.join(sorted(substr))]:
            ans.append([anagram_str,substr])
        is_present[''.join(sorted(substr))].append(substr)  
    return ans

str = raw_input().strip()
print anagram_substring(str)

There's no need to use a list and convert it to a set, you can use a set from the start.

Also, you're checking for every entry if it's in the list as an anagram and adding it to the answer, which is inefficient. You can do this in a faster way by using a dictionary that has the sorted substr as key and pushing the values in there.

from collections import defaultdict
import itertools

def anagram_substring(str):
    substr_list = set([])
    anagrams = defaultdict(list)

    for i in xrange(len(str)):
        for j in xrange(i + 2, len(str) + 1):
            substr_list.add(str[i:j])

    for substr in substr_list:
        anagrams[''.join(sorted(substr))].append(substr)

    return [values for key, values in anagrams.iteritems() if len(values) > 1]

str = raw_input().strip()
print anagram_substring(str)

StackExchange Code Review Q#159417, answer score: 2