Count palindrome substrings

Question

Given a string S, count and return the number of substrings of S that are palindromes. Single length substrings are also palindromes. We just have to count the substring that are palindrome.

INPUT: aba
OUTPUT: 4
EXPLANATION: String aba has a,b,a,aba as palindromic substrings.

My code is running correctly but I need more efficient code.

public class PalindromeSubstrings {
 public static int countPalindromeSubstrings(String s)
 {
 String a;
 int countSubs=s.length();
 for(int i=0;i<s.length();i++)
 {
 for(int j=i+2;j<=s.length();j++)
 {
 a=s.substring(i,j);
 countSubs+=count(a);
 }
 }
 return countSubs;
 }
 public static int count(String a)
 {
 for(int i=0;i<a.length();i++)
 {
 if(a.charAt(i)!=a.charAt(a.length()-1-i))
 return 0;
 }
 return 1;
 }
}

Answer 1

1. Shouldn't the count method be called isPalindrome?
2. count/isPalindrome only needs to iterate over half the string: i<a.length()/2. (Make sure to test it, it might be <=)
3. You should use boolean instead of int for isPalindrome.
4. There's no need to create a temporary a variable in countPalindromeSubstrings.
5. count would probably make more sense than countSubs.
6. The whitespace seems off.
7. Keep your indentation consistent (I'm using 4 spaces since that's what I prefer and it's hard to tell what you prefer [I actually prefer tabs, but spaces are strongly recommended on this site]).
8. Stay consistent with your brace style. I personally prefer K&R/Egyptian/whatever braces (the style you use around the class), but it seems you prefer ANSI/Allman/whatever braces (the style you use everywhere else in this code), so I'll use that.

Point 2 should provide about double the speed; the others probably won't change the speed much, put should still probably be made.

Result:

public class PalindromeSubstrings
{
 public static int countPalindromeSubstrings(String s)
 {
 int count = s.length();
 for(int i = 0; i < s.length(); i++)
 {
 for(int j = i+2; j <= s.length(); j++)
 {
 countSubs += isPalindrome(s.substring(i, j));
 }
 }
 return countSubs;
 }
 public static int isPalindrome(String a)
 {
 for(int i = 0; i < a.length() / 2; i++)
 {
 if(a.charAt(i) != a.charAt(a.length() - 1 - i))
 return 0;
 }
 return 1;
 }
}

• sahil mehta: Your solution is working but it is exceeding the time limit. It does make a difference but it is not significant!!
• Solomon Ucko: @sahilmehta, I was pretty sure it wouldn't be enough, but it would still help, as I didn't improve the performance much. However, it improves the code style, which should make it easier to make additional improvements.

Answer 2

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.