Strings Rearrangement

Given an array of equal-length strings, you'd like to know if it's possible to rearrange the order of the elements in such a way that each consecutive pair of strings differ by exactly one character. Return true if it's possible, and false if not.

Note

You're only rearranging the order of the strings, not the order of the letters within the strings!

Example

• For inputArray = ["aba", "bbb", "bab"], the output should be

  strings_rearrangement(inputArray) = false

  There are 6 possible arrangements for these strings:

  • ["aba", "bbb", "bab"]
  • ["aba", "bab", "bbb"]
  • ["bbb", "aba", "bab"]
  • ["bbb", "bab", "aba"]
  • ["bab", "bbb", "aba"]
  • ["bab", "aba", "bbb"]

  None of these satisfy the condition of consecutive strings differing by 1 character, so the answer is false.

• For inputArray = ["ab", "bb", "aa"], the output should be

  strings_rearrangement(inputArray) = true

  It's possible to arrange these strings in a way that each consecutive pair of strings differ by 1 character (eg: "aa", "ab", "bb" or "bb", "ab", "aa"), so return true.

Input/Output

• [input] array.string inputArray

  A non-empty array of strings of lowercase letters.

Solution

PYTHON

import itertools


def check_string(permutation):
    for i in range(len(permutation) - 1):
        if sum([a != b for a, b in zip(permutation[i], permutation[i + 1])]) != 1:
            return False
    return True


def strings_rearrangement(input_array):
    permutations = itertools.permutations(input_array)

    for permutation in permutations:
        if(check_string(permutation)):
            return True
    return False


print(strings_rearrangement(["aba", "bbb", "bab"]))
print(strings_rearrangement(["ab", "bb", "aa"]))

JAVASCRIPT

function solution(inputArray) {
  const permutations = inputArray.reduce(
    (acc, cur) => {
      const newAcc = [];
      acc.forEach((item) => {
        for (let i = 0; i <= item.length; i++) {
          newAcc.push([...item.slice(0, i), cur, ...item.slice(i)]);
        }
      });
      return newAcc;
    },
    [[]]
  );

  return permutations.some((item) => {
    for (let i = 0; i < item.length - 1; i++) {
      let diff = 0;
      for (let j = 0; j < item[i].length; j++) {
        if (item[i][j] !== item[i + 1][j]) {
          diff++;
        }
      }
      if (diff !== 1) {
        return false;
      }
    }
    return true;
  });
}

print(strings_rearrangement(['aba', 'bbb', 'bab']));
print(strings_rearrangement(['ab', 'bb', 'aa']));