Iterate over the neighborhood of a string Input
A string S of length between 2 and 30. The only letters in the string will be a or b.
Output
All strings within Levenshtein distance 2 of S. You must output all the strings without duplicates but in any order you like.
Example
If S = aaa then the output would be (in any order):
aa
abab
ab
aabba
aaaa
abaa
bbaaa
aba
bbaa
babaa
bba
abaaa
abaab
baaa
baab
baaaa
baba
aabaa
ba
abba
aaba
aabb
abbaa
abb
aabab
aaaaa
aaaab
baaba
a
aaaba
aaabb
aaa
aab
ababa
aaab
bab
baa
baaab

Constraints
Your code must be fast enough that it would run to completion on TIO when S is of length 30.  This is only to stop brute force solutions.
Haskell, 115 109 bytes

-6 thanks to Unrelated String


import Data.List
f=nub.(=&lt;&lt;)g.g
g=(=&lt;&lt;)h.(zip.inits&lt;*&gt;tails)
h(x,y)=[x++b++c|b&lt;-[&quot;a&quot;,&quot;b&quot;,&quot;&quot;],c&lt;-[y,drop 1 y]]

Try it online!
Explanation:

f :: String -&gt; [String]
f=nub    -- delete duplicates
 .(=&lt;&lt;)g -- apply g to every result (get all words with distance &lt;= 2)
 .g      -- apply g once to the input (get all words with distance &lt;= 1)

g :: String -&gt; [String]
g=(=&lt;&lt;)h               -- apply h to every split and flatten the resulting list
 .(zip.inits&lt;*&gt;tails)  -- split the string at every possible position

{- |
h takes a pair of Strings (x,y the input split at some point) and returns all
combinations of x, one of a, b or nothing, and y with the first letter present
or removed
(&quot;he&quot;,&quot;llo&quot;) -&gt; [&quot;heallo&quot;,&quot;healo&quot;,&quot;hebllo&quot;,&quot;heblo&quot;,&quot;hello&quot;,&quot;helo&quot;]
drop 1 is basically the same as tail with the difference that drop 1 [] returns
[] instead of throwing an error
-}
h :: (String,String) -&gt; [String]
h(x,y)=[x++b++c|b&lt;-[&quot;a&quot;,&quot;b&quot;,&quot;&quot;],c&lt;-[y,drop 1 y]]