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

• I found a counter example: ["ca", "ba", "aa", "ab", "ac", "bb"]. This program returns False. The correct answer is True. (The strings can be rearranged as follows: ["ca", "ba", "aa", "ac", "ab", "bb"].) Sorry, Adam... Oct 18 '17 at 21:00
• Could you explain your code with actual text or give the pseudocode?
– Evil
Oct 18 '17 at 21:23
• This doesn't appear to answer the question. This is not a coding site, so answers that consist solely or primarily of code aren't suitable here. We want answers to contain ideas, algorithms, concise pseudocode, and proofs/arguments of correctness. Also I don't see any reason to believe your code is correct. Finally, the question asks whether this algorithm is correct. Your answer says "I don't know if it is correct but I implemented it in Python". That doesn't answer the question.
– D.W.
Oct 18 '17 at 22:52
• The Python code was my original implementation of my algorithm that the OP mentioned. (I am the someone who suggested it). I posted for reference. I could remove it, but I hardly see how that is helpful at this point. Oct 18 '17 at 23:42

By giving each string an ID, For example: ['abc':0, 'bef':1, 'bcc':2, 'bec':3, 'bbc':4, 'bdc':5]

Capture the hamming distance of 0/1 for all qualified string pairs. Now you have [[0, 4], [1, 3], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]

where a map such as this can be produced from it: {0: , 1: , 2: [3, 4, 5], 3: [1, 2, 4, 5], 4: [0, 2, 3, 5], 5: [2, 3, 4]}

This is nothing but a representation of a graph, where as NP-complete part that you iterate through each starting point to exhaustically find one possible path that visit every node once and only once. In this case:

[0, 4, 2, 5, 3, 1] can be one solution

I assume there are some heuristic can be used to shorten search time. In this case, node 0 and 1 only have one connection each. They have to be the starting/ending points, for example. And for those who have 2 connections, ... etc. It doesn't have to be brute-forced.

New contributor
Stone is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.