You could try taking advantage of the fact that, if you remove the first and last letter of a palindrome, then the resulting string will be a palindrome too by storing the indices of a discovered palindrome substring, along with the indices of all substrings that you get from that string with the method mentioned above, in a cache so you don't have to check these substrings separately. This means that you would have to check the substrings in descending order with regard to their length.
public static boolean isPalindrome(String string) {
for (int i = 0; i < string.length() / 2; i++) {
if (string.charAt(i) != string.charAt(string.length() - 1 - i)) {
return false;
}
}
return true;
}
public static int countPalindromeSubstrings(String string) {
/*
A set of lists where each list contains two integers that represent the
first and the last index of a palindrome substring
*/
Set<List<Integer>> palindromeSubstringsIndices = new HashSet<>();
for (int substringLength = string.length(); substringLength > 0; substringLength--) {
for (int startIndex = 0; startIndex + substringLength <= string.length(); startIndex++) {
int endIndex = startIndex + substringLength - 1; //index of last character in substring
List<Integer> currentSubstringIndices = new ArrayList<>();
currentSubstringIndices.add(startIndex);
currentSubstringIndices.add(endIndex);
if (!palindromeSubstringsIndices.contains(currentSubstringIndices)
&& isPalindrome(string.substring(startIndex, endIndex + 1))) {
/*
The termination condition in the following for-loop ensures
that one-character substrings are handled as well
*/
for (int offset = 0; offset < (double) substringLength / 2.0; offset++) {
List<Integer> newPalindromeSubstringIndices = new ArrayList<>();
newPalindromeSubstringIndices.add(startIndex + offset);
newPalindromeSubstringIndices.add(endIndex - offset);
palindromeSubstringsIndices.add(newPalindromeSubstringIndices);
}
}
}
}
return palindromeSubstringsIndices.size();
}
This seems to work, but I have no idea whether it really is faster than your code, or whether the caching and looking up of indexes of known palindrome substrings takes more time in the end than simply iterating through all possible substrings.