--description--

In this lab, you will build a permutation generator that will take a string and return all possible permutations of the characters in the string. For example, the possible permutations of the string cat are cat, cta, act, atc, tac, and tca.

The recursive way of creating permutations of a string works by storing the fixed starting part of the string (prefix), and creating permutations of the rest.

For example, let's consider the word machine. The first round of creating permutations would be made fixing the m as the prefix of the string, and then creating permutations of the rest of the string, achine.

For the rest of the string, permutations continue in the same way. One letter is added to the prefix, maybe the c, so the prefix becomes mc. Then, each of the permutations of ahine is concatenated to the prefix.

This continues until the prefix has all the letters, and the rest of the string is empty, that means one permutation has been created.

Objective: Fulfill the user stories below and get all the tests to pass to complete the lab.

User Stories:

1. You should create a function named permuteString.
2. The permuteString function should take one parameter, a string, and then two parameters with a default value: a prefix value and an empty array for storing and returning the results. The prefix value should be a string used to accumulate characters to form a permutation. The function will be called with one single argument, like permuteString("cat").
3. Inside the function, you should check if the length of the passed string is 0. If it is, push the current prefix to the results and return the results.
4. Iterate over each character in the input string and for each iteration, remove the current character from the string and call the permuteString function recursively with updated arguments to build the remaining permutations.
5. You should return the final results array.
6. You should ensure that the permutations are unique by removing duplicates.

--hints--

You should have a function permuteString.

assert.isFunction(permuteString);

You should use recursion in your permuteString function.

assert.match(permuteString.toString(), /permuteString\s*\(/);

permuteString("far") should return [ "far", "fra", "afr", "arf", "rfa", "raf" ].

assert.sameMembers(permuteString("far"), [ "far", "fra", "afr", "arf", "rfa", "raf" ]);

permuteString("fcc") should return [ "fcc", "cfc", "ccf" ].

assert.sameMembers(permuteString("fcc"), [ "fcc", "cfc", "ccf" ]);

permuteString("p") should return [ "p" ].

assert.deepStrictEqual(permuteString("p"), ["p"]);

permuteString("") should return [""].

let emptyArr= permuteString("");

// 1 because the empty string is being pushed and is a permutation of itself
assert.lengthOf(emptyArr, 1);

permuteString("walk") should return ["walk", "wakl", "wlak", "wlka", "wkla", "wkal", "awlk", "awkl", "alwk", "alkw", "aklw", "akwl", "lawk", "lakw", "lwak", "lwka", "lkaw", "lkwa", "kawl", "kalw", "kwal", "kwla", "klaw", "klwa"]. `.

assert.sameMembers(permuteString("walk"), ["walk", "wakl", "wlak", "wlka", "wkla", "wkal", "awlk", "awkl", "alwk", "alkw", "aklw", "akwl", "lawk", "lakw", "lwak", "lwka", "lkaw", "lkwa", "kawl", "kalw", "kwal", "kwla", "klaw", "klwa"]);

permuteString should return the correct results.

// tests to prevent hard coding
assert.sameMembers(permuteString("road"), [ "road",
  "roda",
  "raod",
  "rado",
  "rdoa",
  "rdao",
  "orad",
  "orda",
  "oard",
  "oadr",
  "odra",
  "odar",
  "arod",
  "ardo",
  "aord",
  "aodr",
  "adro",
  "ador",
  "droa",
  "drao",
  "dora",
  "doar",
  "daro",
  "daor" ]);

assert.sameMembers(permuteString("fog"), [ "fog",
  "fgo",
  "ofg",
  "ogf",
  "gfo",
  "gof" ]);

assert.sameMembers(permuteString("bird"), [ "bird",
  "bidr",
  "brid",
  "brdi",
  "bdir",
  "bdri",
  "ibrd",
  "ibdr",
  "irbd",
  "irdb",
  "idbr",
  "idrb",
  "rbid",
  "rbdi",
  "ribd",
  "ridb",
  "rdbi",
  "rdib",
  "dbir",
  "dbri",
  "dibr",
  "dirb",
  "drbi",
  "drib" ]);

--seed--

--seed-contents--

--solutions--

const permuteString = (str, prefix = "", result = []) => {
  if (str.length === 0) {
    result.push(prefix);
    return result;
  }

  // Sort the string initially to group duplicates
  const sortedStr = str.split("").sort().join("");

  for (let i = 0; i < sortedStr.length; i++) {
    if (i > 0 && sortedStr[i] === sortedStr[i - 1]) {
      // Skip duplicate characters
      continue;
    }

    const rem = sortedStr.slice(0, i) + sortedStr.slice(i + 1);
    permuteString(rem, prefix + sortedStr[i], result);
  }

  return result;
};