fork download
copy 
  1. public class Main {
  2.     public static void main(String[] args) {
  3.         String s = "aaa";
  4.         System.out.println(countPalindromes(s));
  5.     }
  6.  
  7.     public static int countPalindromes(String s) {
  8.     	// i need to Store in a dp[i][j] arr where each cell repr each and every possible subtring.. 
  9.     	// Then check validity and store true or false for each substring. 
  10.     	// base case dp[i][i] = length of substring = 1,  like declaring base case dp[1]=arr[0] for max subarr
  11.  
  12.         int n = s.length();
  13.         boolean[][] dp = new boolean[n][n];
  14.         int count = 0;
  15.  
  16.         // Length = 1 (single characters)
  17.         for (int i = 0; i < n; i++) {
  18.             dp[i][i] = true;
  19.             count++;
  20.         }
  21.  
  22.         // Length = 2
  23.         // condition for length 2 to be true is s[i]==s[i+1]
  24.         for (int i = 0; i < n - 1; i++) {
  25.             if (s.charAt(i) == s.charAt(i + 1)) {
  26.                 dp[i][i + 1] = true;
  27.                 count++;
  28.             }
  29.         }
  30.  
  31.         // Length >= 3
  32.         for (int len = 3; len <= n; len++) {
  33.             for (int i = 0; i <= n - len; i++) {
  34.                 int j = i + len - 1;
  35.  
  36.                 if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
  37.                     dp[i][j] = true;
  38.                     count++;
  39.                 }
  40.             }
  41.         }
  42.  
  43.         return count;
  44.     }
  45. }
Success #stdin #stdout 0.07s 54540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6
https://ideone.com/G3pKo9
language:
Java (HotSpot 12)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!