647. Count palindromic substring

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int countSubstrings(char *s) {
  int n = strlen(s);
  int count = 0;
  bool *dp = calloc(n * n, sizeof(bool)); // dp[i * n + j]: s[i..j] is a palindrome

  for (int i = 0; i < n; i++) {
    dp[i * n + i] = true;
    count++;
  }

  for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
      int j = i + len - 1;

      if (s[i] == s[j] && (len == 2 || dp[(i + 1) * n + (j - 1)])) {
        dp[i * n + j] = true;
        count++;
      }
    }
  }

  free(dp);
  return count;
}

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  int countSubstrings(string s) {
    int n = s.size();
    int count = 0;
    vector<vector<bool>> dp(n, vector<bool>(n, false));

    for (int i = 0; i < n; i++) {
      dp[i][i] = true;
      count++;
    }

    for (int len = 2; len <= n; len++) {
      for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;

        if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1])) {
          dp[i][j] = true;
          count++;
        }
      }
    }

    return count;
  }
};

package dp

func countSubstrings(s string) int {
    n := len(s)
    count := 0
    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)
    }

    for i := 0; i < n; i++ {
        dp[i][i] = true
        count++
    }

    for length := 2; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1

            if s[i] == s[j] && (length == 2 || dp[i+1][j-1]) {
                dp[i][j] = true
                count++
            }
        }
    }

    return count
}

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            count++;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;

                if (s.charAt(i) == s.charAt(j) && (len == 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }

        return count;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function (s) {
  const n = s.length;
  let count = 0;
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));

  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
    count++;
  }

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;

      if (s[i] === s[j] && (len === 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        count++;
      }
    }
  }

  return count;
};

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        dp = [[False] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = True
            count += 1

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    count += 1

        return count

impl Solution {
    pub fn count_substrings(s: String) -> i32 {
        let b = s.as_bytes();
        let n = b.len();
        let mut count = 0;
        let mut dp = vec![vec![false; n]; n];

        for i in 0..n {
            dp[i][i] = true;
            count += 1;
        }

        for len in 2..=n {
            for i in 0..=n - len {
                let j = i + len - 1;

                if b[i] == b[j] && (len == 2 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    count += 1;
                }
            }
        }

        count
    }
}