Solving Algorithmic Problems

Description   Solution: DP w/ Bitmasks Memoize each  dp(mask, prevIndex) , where mask  = bitmask which indicates which numbers we have used so far prevIndex  = index of the previous number in the permutation For each  dp(mask, prevIndex) , go through each number and try each unused number that is valid for the current sequence. Count the total number of ways. Time Complexity:  O(2^n * n^2) Space Complexity:  O(2^n * n) var specialPerm = function ( nums ) { let n = nums.length, fullMask = ( 1 << n) - 1 ; let memo = Array ( 1 << n).fill( 0 ).map( () => Array (n).fill(- 1 )), MOD = 10 ** 9 + 7 , res = 0 ; for ( let i = 0 ; i < n; i++) { res = (res + dp( 1 << i, i)) % MOD; } return res; function dp ( mask, prevIndex ) { if (mask === fullMask) return 1 ; if (memo[mask][prevIndex] !== - 1 ) return memo[mask][prevIndex]; let ans = 0 ; for ( let i = 0 ; i < n; i++) { if (...

Description   Solution: Bitmasks & Hashmap Since there are only 26 lowercase characters, we can keep track of each word's unique characters in a bitmask. Use a hashmap to count the number of occurances of each bitmask. From the occurances of each bitmask, we can find the number of similar pairs. n = number of words ,  m = max(words[i].length) Time Complexity:  O(nm)  105ms Space Complexity:  O(n)  44.9MB var similarPairs = function ( words ) { let count = new Map (), ans = 0 ; for ( let word of words) { let mask = getMask(word); let occurances = count.get(mask) || 0 ; ans += occurances; count.set(mask, occurances + 1 ); } return ans; }; function getMask ( word ) { let mask = 0 ; for ( let i = 0 ; i < word.length; i++) { let charcode = word[i].charCodeAt() - 97 ; mask |= ( 1 << charcode); } return mask; }

Description   Solution: DP w/ Bitmasks Memoize each  dp(mask, prevNum) , where mask = bitmask of numbers we have taken in nums prevNum is the last number in the current permuation For each  dp(mask, prevNum) , Go through every  nums[i]  where  prevNum + nums[i]  is a perfect square Count the number of permuations that are successful How to handle duplicate permutations : When we add a new number to the sequence, use a set to keep track of which numbers we have used. For e.g: The current sequence is  [5] , the remaining numbers left are  [2,2] . We don't want to take  [5,2]  at this level more than once. Time Complexity:  O(2^n * n * n)  67ms Space Complexity:  O(2^n * n)  41.9MB var numSquarefulPerms = function ( nums ) { let n = nums . length , allUsed = ( 1 << n ) - 1 ; let memo = new Map ( ) , res = 0 , used = new Set ( ) ; for ( let i = 0 ; i < n ; i ++ ) { if...