If you look at the current code complexity, it is O(n**2)
in space complexity (since all substrings need to be saved).
Also, it is O(n**2)*O(k*log(k))
in time complexity, where O(n**2)
is time to generate each substring for original string of length n
, and O(k*log(k))
is time complexity to sort each substring of length k
and save it as a key to be checked against later on.
In the worst case, k
will approach n
, so your time complexity would be O(log(n)*n**3)
for the overall solution.
However, instead of sorting the keys, if you could just look up the keys for each substring, and compare against their values in other substrings, you would be good to go.
So consider solution below, which basically stores the count of each character within a substring in a Counter dictionary, and compares the Counters. Creation of counter as well as comparision of it is an O(k)
operation. So that, the overall time complexity becomes O(n**3) in worst case.
Also note, your original output in the problem statement needs to be corrected: 'dapav', 'vadap'
is a pair of anagrams that the output in the question is missing.
def find_anagram_substrings(s):
length = len(s)
substrings, substring_chars = [], {}
results = set()
for i in xrange(0, length):
for j in xrange(i+2, length+1):
substring = s[i:j]
substrings.append(s[i:j])
substring_chars[substring] = Counter(substring)
for s1, s2 in product(substrings, substrings):
if s1 != s2 and substring_chars[s1] == substring_chars[s2]:
results.add((s1, s2) if s1 < s2 else (s2, s1))
return results
print find_anagram_substrings("vadapav")
print find_anagram_substrings("gnomeslikelemons")
Coming to the code in the original post, I've added a few suggestions on the naming conventions that could help make it more readable:
from collections import defaultdict
import itertools
# itertools is not used, no need to import
def anagram_substring(str):
substr_list = []
ans = []
# ans by itself does not clarify what it might contain.
# result could be a better choice of variable name
is_present = defaultdict(list)
# is_present is again an ambiguous choice of variable name
# it does not tell what values could it be storing
for i in xrange(len(str)):
# len(str) is used multiple times, can be a variable
for j in xrange(i+2, len(str)+1):
substr_list.append(str[i:j])
substr_list = list(set(substr_list))
# a set can be iterated normally, so why convert it back to 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)
2 <= length(substring) < len(original string)
' is supefluous, because it follows from the preceding sentence: 1-char anagrams can't be distinct, hencelen>1
, and there's only one substring with length equal to the input string, so it couldn't differ from itself, either. \$\endgroup\$"dome"
&"emod"
), not anagrams (like"dome"
&"mode"
). Reverse is a special case of anagram, but not every anagram is a reverse; not if string has more than 2 characters. For example, in"brabant"
your code could find"ab"
&"ba"
, but probably not"bra"
&"rab"
. \$\endgroup\$"barbarian"
the solution should be similar to("bar", "arb", "bra")
. Can your code produce that? \$\endgroup\$