Bonfire No repeats please

Author

Created by Rafase282

Github | FreeCodeCamp | CodePen | LinkedIn | Website | E-Mail

Details

• Difficulty: 4/5

Return the number of total permutations of the provided string that don't have repeated consecutive letters.

For example, 'aab' should return 2 because it has 6 total permutations, but only 2 of them don't have the same letter (in this case 'a') repeating.

Remember to use Read-Search-Ask if you get stuck. Try to pair program. Write your own code.

Useful Links

• Permutations
• RegExp
• Heap's algorithm

function permAlone(str) {
  return str;
}

permAlone('aab');

Problem Explanation:

• The program needs to calculate how many of the permutations do not have consecutive repeated characters in a row.

Hint: 1

• The easiest way is to use Heap's algorithm to recursively get a list of all the permutations.

Hint: 2

• Once you have the list then just create a regular expression to catch the repeating characters.

Hint: 3

• You will want to have the permutations as an array of joined strings instead of separated characters.

Spoiler Alert!

Solution ahead!

Code Solution:

function permAlone(str) {

  // Create a regex to match repeated consecutive characters.
  var regex = /(.)\1+/g;

  // Split the string into an array of characters.
  var arr = str.split('');
  var permutations = [];
  var tmp;

  // FUnction to swap variables' content.
  function swap(index1, index2) {
    tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
  }

  //Generate arrays of permutations using the algorithm.
  function generate(int) {
    if (int === 1) {
      // Make sure to join the characters as we create  the permutation arrays
      permutations.push(arr.join(''));
    } else {
      for (var i = 0; i != int; ++i) {
        generate(int - 1);
        swap(int % 2 ? 0 : i, int - 1);
      }
    }
  }

  generate(arr.length);

  // Filter the array of repeated permutations.
  var filtered = permutations.filter(function(string) {
    return !string.match(regex);
  });

  //Return how many have no repetitions.
  return filtered.length;
}

Code Explanation:

• Explain your code here

Go Home