title: Count Palindrome Sub Strings String
signature: func countPalindromeSubStringsString(str []rune, n int) int {
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 ];
  }