Palindrome Partitioning III - DP - Recursion w/ Memoization [JS]

By on

Description 

Solution: DP - Recursion w/ Memoization

  1. Populate costs, where costs[i][j] = the minimum cost of turning the substring from index i to j into a palindrome.
  2. Memoize each dp(i, k) : the minimum cost to split substring from index i onwards into k different palindromes.

Time Complexity: O(n^3 + n^2 * k) 89ms
Space Complexity: O(n^2 + nk) 46.5MB

var palindromePartition = function(s, k) {
  let n = s.length, costs = Array(n).fill(0).map(() => Array(n));
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      costs[i][j] = getMinCostToPalindrome(i, j);
    }
  }
  let memo = Array(n).fill(0).map(() => Array(k + 1).fill(-1));
  return dp(0, k);
  
  function dp(i, k) {
    if (i === n || k === 0) return i === n && k === 0 ? 0 : Infinity;
    if (memo[i][k] !== -1) return memo[i][k];
    let ans = Infinity;
    for (let j = i; j < n; j++) {
      ans = Math.min(ans, dp(j + 1, k - 1) + costs[i][j]);
    }
    return memo[i][k] = ans;
  }
  
  function getMinCostToPalindrome(start, end) { // minimum cost to change substring from start to end into a palindrome
    let cost = 0;
    while (start < end) {
      if (s[start] !== s[end]) cost++;
      start++, end--;
    }
    return cost;
  }
};

javascript
Location: Auckland, New Zealand

Comments

Post a Comment

Popular posts from this blog

Maximum Value of an Ordered Triplet II - Two Solutions [JS]

By on
Description   Solution 1: Prefix Max Summary: Anchor at  nums[j] . We want  nums[i]  and  nums[k]  to be as larger as possible, and  nums[j]  to be as small as possible to ensure the maximum value. Calculate the maximum value on the right of each index  i :  maxRight[i]  = maximum value from index  i  to  n - 1 Go through  nums  from left to right and take each element as  nums[j] . Keep track of the maximum value on the left. Get the maximum value on the left and right of  nums[j] . Record the maximum value. Time Complexity:  O(n) Space Complexity:  O(n) var maximumTripletValue = function ( nums ) { let n = nums.length, maxRight = [...nums]; for ( let i = n - 2 ; i >= 0 ; i--) { maxRight[i] = Math .max(nums[i], maxRight[i + 1 ]); } let maxLeft = 0 , ans = 0 ; for ( let j = 0 ; j < n; j++) { if (j > 0 && j < n - 1 ) { ans = Math .max(an...
Read more

Maximum Sum of Distinct Subarrays With Length K - Sliding Window w/ Two Pointers & Set [JS]

By on
Description  Solution: Sliding Window w/ Two Pointers & Set Maintain a sliding window of unique numbers with maximum size of  k . We can store the numbers in the window in a hashset. When we move the right pointer up, move the left pointer up until: all numbers in the window are unique the window size  <= k Time Complexity:  O(n)  246ms Space Complexity:  O(k)  71.5MB var maximumSubarraySum = function ( nums, k ) { let set = new Set (), sum = 0 ; let ans = 0 , n = nums.length; for ( let j = 0 , i = 0 ; j < n; j++) { sum += nums[j]; while (set.has(nums[j]) || j - i >= k) { sum -= nums[i]; set.delete(nums[i]); i++; } set.add(nums[j]); if (j - i + 1 === k) ans = Math .max(ans, sum); } return ans; };
Read more

Sum of Prefix Scores of Strings - Trie [JS]

By on
Description   Solution: Trie Store each word in a trie. For every node in the trie, keep track of the number of words it is part of. Since we stored the count of words on every node, we can calculate the count of every prefix for every word on the fly. n = number of words ,  m = max(words[i].length) Time Complexity:  O(nm) Space Complexity:  O(26^m)  at worst var sumPrefixScores = function ( words ) { let trie = new Trie(); for ( let word of words) { trie.add(word); } let n = words.length, res = Array (n); for ( let i = 0 ; i < words.length; i++) { res[i] = trie.getScore(words[i]); } return res; }; class TrieNode { constructor ( ) { this .children = {}; this .count = 0 ; } } class Trie { constructor ( ) { this .root = new TrieNode(); } add ( word ) { let node = this .root; for ( let i = 0 ; i < word.length; i++) { node = node.children; let char = word[i]; if (...
Read more

Count Subarrays With Median K - Count Left & Right Balance [JS]

By on
Description   Solution: Count Left & Right Balance For a subarray to have median of  k : The subarray must contain  k . k  must be the middle element (if odd) or lower mid element (if even). Create subarrays revolving around  nums[i] = k . How do we find whether  k  is the mid/lower mid element? Starting from  k , count the "balance" on the left and right of  k . If  nums[i] < k , add  -1  to the balance. If  nums[i] > k , add  1  to the balance. If  k  is the mid element, the left balance + right balance =  0 . If  k  is the lower mid element, left balance + right balance =  1 . Store the count of left balances in a hashmap. Go through each right balance, Balance = 0 : Count the number of left balances that are equal to ( -right balance ) Balance = 1 : Count the number of left balances that are equal to ( -right balance + 1 ) Time Complexity:  O(n) Space Complexity:...
Read more

Reschedule Meetings for Maximum Free Time I - Sliding Window - Constant Space [JS]

By on
Description   Solution: Sliding Window Maintain a sliding window of size  k + 2  and store the running sum of meetings within the window. Within each window, move all meetings as left as possible or right as possible such that there is no space in between the meetings. This maximizes the longest continuous gap. This can be calculated by: last meeting start time - first meeting end time - sum of meeting durations in between first and last meetings. Time Complexity:  O(n) Space Complexity:  O(1) JavaScript function maxFreeTime ( eventTime , k , startTime , endTime ) { const n = startTime . length ; let durationSum = 0 , maxGap = 0 ; for ( let i = 0 ; i < n ; i ++ ) { durationSum += endTime [ i ] - startTime [ i ] ; if ( i >= k ) { durationSum -= endTime [ i - k ] - startTime [ i - k ] ; } if ( i >= k - 1 ) { const lastMeetingStart = i === n - 1 ? eventTime : startTime [ i +...
Read more