Java O(n^2) time O(1) space solution with comments.


  • 4
    X
    public int countSubstrings(String s) {
        int sum = 0;
        // Loop across different middle points.
        for (int i = 0; i < s.length(); i++) {
          // Find all odd length palindrome with i as middle point.
          sum += findPalindromic(s, i, i);
          // Find all even length palindrome with i and i+1 as middle point.
          sum += findPalindromic(s, i, i + 1);
        }
        return sum;
      }
    
      // Expend from the current mid point to all of its low and high positions.
      private int findPalindromic(String s, int left, int right) {
        int count = 0;
        // Increase count if the substring is a validate palindrome.
        while (left >= 0 && right < s.length() && s.charAt(left--) == s.charAt(right++))
          count++;
        return count;
      }
    

  • 0

    @xiyunyue2 thank you for your answer. Could you kindly share the recursive equation that you used? Or, was there none?


  • 0

    Also, was the intuition of working with the middle element (i) because of the fact that the left and right parts of a palindrome are same?


  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.