# 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.

• May we use any pair of printable characters instead of a and b? Dec 13, 2020 at 12:16
• Are you sure the constraint is enough to stop brute-force solutions? Length 20 gives about a million possible strings, and I can imagine a solution testing all of those within a minute on TIO.
– xnor
Dec 13, 2020 at 12:25
• The famous Swedidsh pop group abba is missing from your example output, and so are baba, abaab, aabab and ababa. Dec 13, 2020 at 12:34
• @SunnyMoon My understanding is that within implies $\le2$. Dec 13, 2020 at 13:14
• @Arnauld Hopefully all fixed now.
– user7467
Dec 13, 2020 at 14:00

• -6 thanks to Unrelated String
import Data.List
f=nub.(=<<)g.g
g=(=<<)h.(zip.inits<*>tails)
h(x,y)=[x++b++c|b<-["a","b",""],c<-[y,drop 1 y]]


Try it online!

Explanation:

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

g :: String -> [String]
g=(=<<)h               -- apply h to every split and flatten the resulting list
.(zip.inits<*>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
("he","llo") -> ["heallo","healo","hebllo","heblo","hello","helo"]
drop 1 is basically the same as tail with the difference that drop 1 [] returns
[] instead of throwing an error
-}
h :: (String,String) -> [String]
h(x,y)=[x++b++c|b<-["a","b",""],c<-[y,drop 1 y]]

• -4 Dec 14, 2020 at 1:20
• ...actually it's -6 if you just get rid of m altogether Dec 14, 2020 at 1:24
• I totally forgot you could do that. :O Dec 14, 2020 at 1:30
• Would you mind adding a little bit of explanation?
– user7467
Dec 14, 2020 at 10:53

# Charcoal, 66 bytes

⊞υθ≔⟦θ⟧ηＦη«≔⟦⟧ζＦＬιＦabＦ³⊞ζ⭆ι⎇⁻ξκν…⁺λνμＦab⊞ζ⁺ικＦζ¿¬№υκ«⊞υκ¿⁼ιθ⊞ηκ»»υ


Try it online! Link is to verbose version of code. Explanation:

⊞υθ


Push the input to the predefined empty list as the first result.

≔⟦θ⟧ηＦη«


Start a breadth-first search using the input.

≔⟦⟧ζ


Start collecting potential new results.

ＦＬιＦabＦ³


Loop over each index, each potential insert/edit, and each operation (0=delete, 1=edit, 2=insert).

⊞ζ⭆ι⎇⁻ξκν…⁺λνμ


Apply the specified operation to the appropriate index of the current string.

Ｆab⊞ζ⁺ικ


Also consider appending either of a and b to the current string.

Ｆζ¿¬№υκ«


For each string that has not been seen before, ...

⊞υκ


... push it to the result string, ...

¿⁼ιθ⊞ηκ


... and if we're modifying the original input then also push it to the search space.

»»υ


Finally print all the results.

# Python 2, 113 bytes

Takes input as a singleton list containing the string.

s="{k[:i]+c+k[i+w:]for k in %sfor i in range(len(k)+1)for c in['','a','b']for w in(0,1)}"
print eval(s%s%input())


Try it online!

# Python 3, 114 bytes

f=lambda s,d=2,i=0:d*s[i-1:]and{k[:i]+c+k[i+w:]for k in f(s,d-1)for c in['','a','b']for w in(0,1)}|f(s,d,i+1)or{s}


Try it online!

Commented:

f=lambda s,d=2,i=0:      # a recursive function with arguments:
#  - s, the input string
#  - d, the maximal Levensthein distance to s
#  - i, the index of the current operation
d*s[i-1:]and ... or{s} # if d==0 or i>len(s) return a set containing s
# otherwise:
{k[:i]+c+k[i+w:]       #  apply an operation
for k in f(s,d-1)     #   on every string with maximal Levensthein distance d-1
for c in['','a','b']  #   insert / replace with any of '', 'a', 'b'
for w in(0,1)}        #   w==0: c=='': no operation, c!='': insertion
#   w==1: c=='': deletion,     c!='': replacement
| f(s,d,i+1)           #  union this to the result of applying an operation at a larger index

• Do you think this code can be made iterative? Just out of interest.
– user7467
Dec 13, 2020 at 15:07
– ovs
Dec 13, 2020 at 15:28

# JavaScript (ES6),  137 134 131  123 bytes

Expects a string with 0/1 instead of a/b. Returns an Object whose keys (and values) are the output strings.

f=(s,k=2,o={},p='')=>[...o[s]=s].map((c,i)=>k&&[p+(q=s.slice(i+1)),p+(C=c^1)+q,(p+=c)+0+q,p+1+q,C+s].map(s=>f(s,k-1,o)))&&o


Try it online!

### Commented

This is a naive and rather lengthy implementation that just builds all the strings recursively.

f = (                         // f is a recursive function taking:
s,                          //   s = input string
k = 2,                      //   k = counter
o = {},                     //   o = an object used to store the results
p = ''                      //   p = current prefix
) =>                          //
[...o[s] = s]               // save s into o and split s
.map((c, i) =>              // for each character c at position i in s:
k &&                      //   abort if k = 0
[                         //   otherwise, build an array:
p +                     //     remove c by concatenating the prefix p
(q = s.slice(i + 1)),   //     with the suffix q
p + (C = c ^ 1) + q,    //     modify c
(p += c) + 0 + q,       //     insert '0' after c (and update p)
p + 1 + q,              //     insert '1' after c
C + s                   //     prepend the modified c at the beginning
//     (this case is not covered by the insertions)
]                         //   end of array
.map(s => f(s, k - 1, o)) //   do a recursive call for each string in there
)                           // end of map()
&& o                        // return o

• I don't know javascript but how does your code avoid duplicates?
– user7467
Dec 13, 2020 at 14:23
• @Anush It uses a dictionary as a set.
– Neil
Dec 13, 2020 at 14:56

# Ruby 2.7, 115 109 bytes

Port of ovs's answer in Python!

f=->s,d=2,i=0{d>0&&s[i-1]?['',?a,?b].product(f[s,d-1],[0,1]).map{_2[...i]+_1+"#{_2[i+_3..]}"}|f[s,d,i+1]:[s]}


Try it online!

TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves 3 bytes, and we've begin-less ...i and end-less i+_3.. ranges, which saves 3 more bytes!

import Data.List
nub.(g=<<).g
g(h:t)=t:((:)<\$>"ab"<*>[h:t,t])++map(h:)(g t)
g _=["a","b"]


Try it online!

The helper function g recursively generates all strings at Levenshtein distance 1.

# K (ngn/k), 78 bytes

{?"ab"@?,/e'e"b"=x}
e:{?,/(~+x==#x;{y,x,z}.',/0 1,/:\:(0,'!1+#x)_\:x;x_/:!#x)}


Try it online!