title: Count Palindrome Sub Strings String
signature: class Solution {
  
      public Integer countPalindromeSubStringsString(ArrayList<Character> str, Integer 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.extension: java
question_info.entry_fn_name: countPalindromeSubStringsString
question_info.entry_cls_name: Solution
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}}]
question_info.test_code: import static java.util.Map.entry;  
  import java.util.*;
  import java.lang.*;
  // TESTING CODE 
  // ============================================
  class QuestionEvaluator {
      public static String validateSolution(ArrayList<Character> str, Integer n, Integer expected){
          try{
              Driver driver = new Driver();
              if (driver.run(str, n,expected)){
                  return "PASSED";
              }
              return "FAILED";
              
          } catch (Exception exception_obj){
              return exception_obj.getClass().getSimpleName();
          }
  
      }
      public static void main(String[] args) {
          String result;
          result = validateSolution(new ArrayList<>(Arrays.asList('E', 'E', 'J', 'P', 'T', 'U', 'X', 'Y', 'Z', 'e', 'f', 'h', 'l', 'm', 'n', 'o', 'z')), 11, 1);
          System.out.println(String.format("%s%s","TEST-0...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('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);
          System.out.println(String.format("%s%s","TEST-1...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('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);
          System.out.println(String.format("%s%s","TEST-2...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('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);
          System.out.println(String.format("%s%s","TEST-3...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('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);
          System.out.println(String.format("%s%s","TEST-4...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('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);
          System.out.println(String.format("%s%s","TEST-5...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('C', 'C', 'D', 'F', 'L', 'M', 'P', 'X', 'a', 'f', 'i', 'j', 'w')), 9, 1);
          System.out.println(String.format("%s%s","TEST-6...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('7', '9', '0', '2', '8', '0', '7', '5', '9', '4', '5', '4', '8', '1', '9', '5', '3', '2', '4', '1', '2')), 16, 1);
          System.out.println(String.format("%s%s","TEST-7...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('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);
          System.out.println(String.format("%s%s","TEST-8...",result));    
      
          result = validateSolution(new ArrayList<>(Arrays.asList('m', 'X', 'N', 'M')), 3, 0);
          System.out.println(String.format("%s%s","TEST-9...",result));    
      
      }
  }
  
  class Driver{
      public boolean run(ArrayList<Character> str, Integer n, Integer expected){
  
          PLACEHOLDER_CLS_NAME sol = new PLACEHOLDER_CLS_NAME();
          return validateSolution(sol.PLACEHOLDER_FN_NAME(str, n),expected);
      }
      
      public boolean validateSolution(Integer actual, Integer expected){
          return actual.equals(expected);
      }
  }
  
  
  // SOLUTION CODE
  // ============================================
  PLACEHOLDER_CODE_BODY
question_info.test_case_ids: 0 1 2 3 4 5 6 7 8 9
question_info.commands: java __FILENAME__