title: Count Palindrome Sub Strings String
signature: countPalindromeSubStringsString(str, n) {
test_code: import 'dart:convert';
  
  // SOLUTION CODE
  // ============================================
  PLACEHOLDER_CODE_BODY
  
  // TESTING CODE 
  // ============================================
  bool validateSolution(int actual, int expected){
      return actual.toString() == expected.toString();
  }
  
  String driver(str, n, int expected){
      try
      {
          if (validateSolution(PLACEHOLDER_FN_NAME(str, n), expected)){
              return "PASSED";
          }
          return "FAILED";
      }catch(exception_object){
          return exception_object.runtimeType.toString();
      }
  }
  
  int main() {
  
      print("TEST-0...${driver(
          ['E', 'E', 'J', 'P', 'T', 'U', 'X', 'Y', 'Z', 'e', 'f', 'h', 'l', 'm', 'n', 'o', 'z'], 11, 
          1)
      }");
  
      print("TEST-1...${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("TEST-2...${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("TEST-3...${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("TEST-4...${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("TEST-5...${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("TEST-6...${driver(
          ['C', 'C', 'D', 'F', 'L', 'M', 'P', 'X', 'a', 'f', 'i', 'j', 'w'], 9, 
          1)
      }");
  
      print("TEST-7...${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("TEST-8...${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("TEST-9...${driver(
          ['m', 'X', 'N', 'M'], 3, 
          0)
      }");
  
      return 0;
  }
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 ];
  }