title: Count Palindrome Sub Strings String
signature: function countPalindromeSubStringsString(str, n) {
test_code: 
  
  // SOLUTION CODE
  // ============================================
  PLACEHOLDER_CODE_BODY
  
  // TESTING CODE 
  // ============================================
  function convertToString(value) {
      return JSON.stringify(value, function (key, val) {
          if (val instanceof Set) {
              return Array.from(val);
          } return val;});
  }
  
  function validateSolution(actual, expected){
      return convertToString(actual)===convertToString(expected);
  }
  
  function driver(str, n, expected){
      try{
          if (validateSolution(PLACEHOLDER_FN_NAME(str, n),expected)){
              return "PASSED";
          }
          return "FAILED";
      } catch (error) {
        return error.name;
      }
      
  }
      
  function main(){
    let result = '';
    result = driver(['E', 'E', 'J', 'P', 'T', 'U', 'X', 'Y', 'Z', 'e', 'f', 'h', 'l', 'm', 'n', 'o', 'z'], 11, 1);
    console.log(`TEST-0...${result}`);
  
    result = driver(['8', '7', '3', '4', '9', '5', '3', '1', '4', '0', '6', '8', '2', '5', '8', '3', '5', '2', '8', '6', '6', '3', '5', '7', '5', '5', '3', '7'], 27, 3);
    console.log(`TEST-1...${result}`);
  
    result = driver(['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'], 23, 211);
    console.log(`TEST-2...${result}`);
  
    result = driver(['f', 'E', 'e', 'z', 'B', 'o', 'i', 'v', 'K', 'u', 'P', 'C', 'z', 'f', 'k', 'J', 't', 'R', 't', 'A', 'f', 'G', 'D', 'X', 'H', 'e', 'p', 'l', 'l', 'k', 'Z', 'Y', 'u', 'g', 'H', 'C', 'f', 'J', 'H', 'W'], 27, 1);
    console.log(`TEST-3...${result}`);
  
    result = driver(['0', '0', '0', '1', '1', '1', '1', '1', '1', '2', '2', '2', '3', '3', '3', '3', '3', '4', '4', '4', '4', '4', '4', '5', '5', '5', '5', '6', '6', '7', '7', '9', '9', '9', '9', '9', '9'], 35, 60);
    console.log(`TEST-4...${result}`);
  
    result = driver(['1', '0', '1', '1', '0', '0', '1', '1', '1', '0', '1', '0', '1', '1', '0', '1', '0', '1', '1', '1', '1', '1', '0', '1', '1', '0', '1', '0', '1', '1', '0', '0', '1', '0', '1', '0', '0', '0', '0', '0', '1', '1', '0', '1', '0', '1'], 43, 72);
    console.log(`TEST-5...${result}`);
  
    result = driver(['C', 'C', 'D', 'F', 'L', 'M', 'P', 'X', 'a', 'f', 'i', 'j', 'w'], 9, 1);
    console.log(`TEST-6...${result}`);
  
    result = driver(['7', '9', '0', '2', '8', '0', '7', '5', '9', '4', '5', '4', '8', '1', '9', '5', '3', '2', '4', '1', '2'], 16, 1);
    console.log(`TEST-7...${result}`);
  
    result = driver(['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'], 32, 289);
    console.log(`TEST-8...${result}`);
  
    result = driver(['m', 'X', 'N', 'M'], 3, 0);
    console.log(`TEST-9...${result}`);
  
    process.exit(0);
  };
  
  if (require.main === module) {
    main();
  }
source_py: def count_palindrome_sub_strings_string(str, n):
      dp = [[0 for x in range(n)] for y in range(n)]
      P = [[False for x in range(n)] for y in range(n)]
      for i in range(n):
          P[i][i] = True
      for i in range((n - 1)):
          if (str[i] == str[(i + 1)]):
              P[i][(i + 1)] = True
              dp[i][(i + 1)] = 1
      for gap in range(2, n):
          for i in range((n - gap)):
              j = (gap + i)
              if ((str[i] == str[j]) and P[(i + 1)][(j - 1)]):
                  P[i][j] = True
              if (P[i][j] == True):
                  dp[i][j] = (((dp[i][(j - 1)] + dp[(i + 1)][j]) + 1) - dp[(i + 1)][(j - 1)])
              else:
                  dp[i][j] = ((dp[i][(j - 1)] + dp[(i + 1)][j]) - dp[(i + 1)][(j - 1)])
      return dp[0][(n - 1)]
source_cpp: int count_palindrome_sub_strings_string(vector<char> str, int n) {
    int dp [ n ] [ n ];
    memset ( dp, 0, sizeof ( dp ) );
    bool P [ n ] [ n ];
    memset ( P, false, sizeof ( P ) );
    for ( int i = 0;
    i < n;
    i ++ ) P [ i ] [ i ] = true;
    for ( int i = 0;
    i < n - 1;
    i ++ ) {
      if ( str [ i ] == str [ i + 1 ] ) {
        P [ i ] [ i + 1 ] = true;
        dp [ i ] [ i + 1 ] = 1;
      }
    }
    for ( int gap = 2;
    gap < n;
    gap ++ ) {
      for ( int i = 0;
      i < n - gap;
      i ++ ) {
        int j = gap + i;
        if ( str [ i ] == str [ j ] && P [ i + 1 ] [ j - 1 ] ) P [ i ] [ j ] = true;
        if ( P [ i ] [ j ] == true ) dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] + 1 - dp [ i + 1 ] [ j - 1 ];
        else dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] - dp [ i + 1 ] [ j - 1 ];
      }
    }
    return dp [ 0 ] [ n - 1 ];
  }