permAlone

Hard · String Manipulations · 4 test cases

Return the number of total permutations of the provided string that don't have repeated consecutive letters. Assume that all characters in the provided string are unique.

Examples

permAlone('aab') → 2
permAlone('aaa') → 0
permAlone('aabb') → 8

Starter code

function permAlone(str) {

}

Complexity of the optimal solution

Time O(n! * n), space O(n! * n). This solution uses Heap's algorithm to generate all n! permutations of the string. Storing these permutations requires O(n! * n) space. It then iterates through all permutations, performing a regex test, resulting in a time complexity of O(n! * n).

Solve permAlone in the browser