Problem statement

https://binarysearch.com/problems/Generate-Anagram-Substrings/

Solution

Do bruteforce here: for every substring keep in defaultdict its sorted version. Then take all elements where we have more than one element.

Complexity

It is O(n^3 log n) for time and O(n^2) for space.

Code

class Solution:
    def solve(self, s):
        n = len(s)
        d = defaultdict(list)
        for x in range(1, n):
            for i in range(n - x + 1):
                cand = s[i:i+x]
                d["".join(sorted(cand))] += [cand]

        ans = []
        for x in d:
            if len(d[x]) > 1:
                ans += d[x]

        return sorted(ans)

Remark

We can also use rolling hash here to make it O(n^2 log n) time.