# Rearranging strings so that the Hamming distance between them is 1

This is a question from CodeFights.com:

Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character.

Example

• For inputArray = ["aba", "bbb", "bab"], the output should be stringsRearrangement(inputArray) = false; All rearrangements don't satisfy the description condition. (sic)

• For inputArray = ["ab", "bb", "aa"], the output should be stringsRearrangement(inputArray) = true. Strings can be rearranged in the following way: "aa", "ab", "bb".

I found an exponential-time algorithm, but is there a polynomial-time algorithm? Is this problem NP-complete?

I know that a closely related problem, the Hamming Salesman Problem (HTSP), is NP-complete, and this problem is certainly reducible to HTSP, but I don't know if HTSP is reducible to this one.

• Please don't use "EDIT:" or strikeout. Instead, revise the question to read well for someone who encounters it for the first time. Incorporate your edits into the text rather than marking them with "EDIT:". Anything that is no longer relevant should be deleted. Make sure it's clear what the question is. You don't need to mark changes or use strikeout to preserve old versions; we have revision history for that (see the "edited..." link under the question). See cs.meta.stackexchange.com/q/657/755 for more. – D.W. Oct 19 '17 at 15:42

Grid graphs are finite node-induced graphs of the infinite planar grid (whose vertices are integral points, and two vertices are linked when their Euclidean distance is 1). A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter proved that the Hamiltonian path problem on grid graphs is NP-complete.

To reduce that to your problem, suppose the grid graph has $m$ rows and $n$ columns. The $i$-th row is labeled with the string $a^ib^{m-i}$, and the $j$-th column is labeled with the string $a^jb^{n-j}$. Then a vertex corresponds to the concatenation of the two labels of its row and column. Now it is easy to show the unit disk graph under Hamming distance over all these concatenated strings is exactly the same as the original grid graph.

I am the someone who suggested the (apparently, now, failing algorithm). Here is a "reference implementation" in Python:

def consecutive(str1, str2): # are two strings consecutive?
if str1 == str2:
return False  # identical strings are not consecutive
for i, L in enumerate(str1):
if L == str2[i]:  #compare strings one char at a time
continue
else:  # if the chars aren't the same
str2 = list(str2)
str2[i] = L           # swap the letter of str2 with
str2 = "".join(str2)  # one from str2, and compare
return str1 == str2   # if now strs are the same
return True                   # they are consecutive

def stringsRearrangement(inputArray):

ordered = [inputArray]
left = inputArray[1:]

previous_left = len(left) + 1 # sets the first iteration
# of while loop to true

while previous_left > len(left):  # less items than last iteration
previous_left = len(left)
for i,string in enumerate(left): # iter through left
if consecutive(ordered[-1], string): # try to move item
ordered.append(left.pop(i))      # from left to ordered
break
elif consecutive(ordered, string):
ordered.insert(0, left.pop(i))
break

while left:                   # if still items in left
previous_left = len(left) # to check if left is decreasing
for i,string in enumerate(ordered): #iter thru ordered
if consecutive(string, left): #to find something in left
try:                         # that can be inserted
if consecutive(left, ordered[i+1]):
ordered.insert(i+1, left.pop(0))
break
except IndexError:  #if
ordered.append(left.pop(0))
if previous_left == len(left): #if nothing found
break
return not (bool(left)) # true if left is empty


I'm not sure how one would prove that it always works -- but I also cannot find a failing input.

-- EDIT

Could you explain your code with actual text or give the pseudocode?