publicintcountSubstrings(String s) { // Assume s is not null intn= s.length(); intcount=0; for (inti=0; i < n; ++i) { for (intj= i; j < n; ++j) { // check if substring [i, j] is palindromic if (isPalindromic(s, i, j)) ++count; } } return count; }

privatebooleanisPalindromic(String s, int lo, int hi) { intn= hi - lo + 1; for (inti=0; i < n / 2; ++i) { if (s.charAt(lo + i) != s.charAt(hi - i)) returnfalse; } returntrue; }

publicintcountSubstrings(String s) { // Assume s is not null intn= s.length(); intcount=0; for (inti=0; i < n; ++i) { count += countPalindrome(s, i, i); // odd length count += countPalindrome(s, i, i + 1); // even length } return count; }

privateintcountPalindrome(String s, int lo, int hi) { intn= s.length(); intcount=0; while (lo >= 0 && hi < n && s.charAt(lo) == s.charAt(hi)) { ++count; --lo; ++hi; } return count; }