1
/**
2
 * @param {string} s
3
 * @return {boolean}
4
 */
5
var checkPartitioning = function (s) {
6
  // create a dp that will represent the starting and ending index of a substring
7
  // if dp[i][j] is true that means that the string starting from i and ending at j is a palindrome
8
  const dp = new Array(s.length)
9
    .fill(null)
10
    .map(() => new Array(s.length).fill(false));
11

12
  // all substrings of length 1 are palindromes so we mark all matching indices as true
13
  for (let i = 0; i < s.length; i++) {
14
    dp[i][i] = true;
15
  }
16

17
  // slowly grow the substring from each index
18
  // we will know the substring is a palindrom if the substring prior was a palindrome
19
  for (
20
    let lengthOfSubString = 2;
21
    lengthOfSubString <= s.length;
22
    lengthOfSubString++
23
  ) {
24
    for (
25
      let startingIndex = 0;
26
      startingIndex + lengthOfSubString <= s.length;
27
      startingIndex++
28
    ) {
29
      // if it's not the same character, then it can not be a palindrome
30
      if (s[startingIndex] !== s[startingIndex + lengthOfSubString - 1])
31
        continue;
32

33
      if (
34
        lengthOfSubString <= 3 ||
35
        // this checks if the prior substring was a palindrome
36
        dp[startingIndex + 1][startingIndex + lengthOfSubString - 2]
37
      ) {
38
        dp[startingIndex][startingIndex + lengthOfSubString - 1] = true;
39
      }
40
    }
41
  }
42

43
  // find out if any 3 of the partitions are palindromes
44
  for (let i = 0; i < s.length; i++) {
45
    for (let j = i + 1; j < s.length; j++) {
46
      if (dp[0][i] && dp[i + 1][j] && dp[j + 1][s.length - 1]) return true;
47
    }
48
  }
49

50
  // if we haven't found a partition, return false
51
  return false;
52
};