title: Count Palindrome Sub Strings String
signature: function count_palindrome_sub_strings_string(str, n)
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 ];
  }
question_info.entry_fn_name: count_palindrome_sub_strings_string
question_info.entry_cls_name: Solution
question_info.test_case_ids: ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
question_info.test_code: 
  
  -- SOLUTION CODE
  -- ============================================
  PLACEHOLDER_CODE_BODY
  
  -- TESTING CODE 
  -- ============================================
  function isCorrect(actual, expected)
      if type(expected) ~= type(actual) then
          return false
      end
      
      if type(expected) == 'table' then
          for k,v_expected in pairs(expected) do
              
              if actual[k] == nil then
                  return false
              end
              local v_actual = actual[k]
              if not isCorrect(v_actual, v_expected) then
                  return false
              end
              actual[k]=nil
          end
      
          if next(actual) then 
              return false
          end
          return true
      else
          return actual == expected
      end
  end
  
  function validateSolution(actual, expected)
      return isCorrect(actual,expected)
  end
  
  function driver(str, n, expected)
      local exec_result;
      local status, error_msg = pcall(function () 
          exec_result=PLACEHOLDER_FN_NAME(str, n) 
      end)
      if status then
          if validateSolution(exec_result,expected) then
              return "PASSED"
          end
          return "FAILED"
      else
          return string.format("ERROR=%s",string.gsub(error_msg,".*:[%d]+: ",""))
      end
  end
      
  function main()
      result = driver({'E', 'E', 'J', 'P', 'T', 'U', 'X', 'Y', 'Z', 'e', 'f', 'h', 'l', 'm', 'n', 'o', 'z'}, 11, 1)
      print(string.format("TEST-0...%s",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)
      print(string.format("TEST-1...%s",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)
      print(string.format("TEST-2...%s",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)
      print(string.format("TEST-3...%s",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)
      print(string.format("TEST-4...%s",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)
      print(string.format("TEST-5...%s",result))
  
      result = driver({'C', 'C', 'D', 'F', 'L', 'M', 'P', 'X', 'a', 'f', 'i', 'j', 'w'}, 9, 1)
      print(string.format("TEST-6...%s",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)
      print(string.format("TEST-7...%s",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)
      print(string.format("TEST-8...%s",result))
  
      result = driver({'m', 'X', 'N', 'M'}, 3, 0)
      print(string.format("TEST-9...%s",result))
  
  end
  
  main()
question_info.test_list: [{"idx": 0, "outputs": 1, "inputs": {"str": ["E", "E", "J", "P", "T", "U", "X", "Y", "Z", "e", "f", "h", "l", "m", "n", "o", "z"], "n": 11}}, {"idx": 1, "outputs": 3, "inputs": {"str": ["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"], "n": 27}}, {"idx": 2, "outputs": 211, "inputs": {"str": ["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"], "n": 23}}, {"idx": 3, "outputs": 1, "inputs": {"str": ["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"], "n": 27}}, {"idx": 4, "outputs": 60, "inputs": {"str": ["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"], "n": 35}}, {"idx": 5, "outputs": 72, "inputs": {"str": ["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"], "n": 43}}, {"idx": 6, "outputs": 1, "inputs": {"str": ["C", "C", "D", "F", "L", "M", "P", "X", "a", "f", "i", "j", "w"], "n": 9}}, {"idx": 7, "outputs": 1, "inputs": {"str": ["7", "9", "0", "2", "8", "0", "7", "5", "9", "4", "5", "4", "8", "1", "9", "5", "3", "2", "4", "1", "2"], "n": 16}}, {"idx": 8, "outputs": 289, "inputs": {"str": ["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"], "n": 32}}, {"idx": 9, "outputs": 0, "inputs": {"str": ["m", "X", "N", "M"], "n": 3}}]