package leetcode;

/**
 * https://leetcode.com/problems/palindromic-substrings/
 */
public class Problem647 {
    public int countSubstrings(String s) {
        return countSubstrings(s, 0, s.length());
    }

    private static int countSubstrings(String s, int i, int j) {
        if (i >= j) {
            return 0;
        }
        String sub = s.substring(i, j);
        int count = 0;
        if (isPalindrome(sub)) {
            count++;
        }
        int a = countSubstrings(s, i + 1, j);
        int b = countSubstrings(s, i, j - 1);
        int c = countSubstrings(s, i + 1, j - 1);
        return count + a + b + c;
    }

    private static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i <= j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Problem647 prob = new Problem647();
        System.out.println(prob.countSubstrings("abc")); // 3
//        System.out.println(prob.countSubstrings("aaa")); // 6
    }
}

@@ -193,16 +193,118 @@
 length()
+, new boolean%5Bs.length() + 1%5D%5Bs.length() + 1%5D,%0A            new Integer%5Bs.length() + 1%5D%5Bs.length() + 1%5D
 );%0A    %7D
@@ -366,16 +366,57 @@
 i, int j
+, boolean%5B%5D%5B%5D processed, Integer memo%5B%5D%5B%5D
 ) %7B%0A    
@@ -544,28 +544,208 @@
 if (
-isPalindrome(sub)) %7B
+processed%5Bi%5D%5Bj%5D) %7B%0A            return 0;%0A        %7D%0A//        if (memo%5Bi%5D%5Bj%5D != null) %7B%0A//            return memo%5Bi%5D%5Bj%5D;%0A//        %7D%0A        if (isPalindrome(sub)) %7B%0A            processed%5Bi%5D%5Bj%5D = true;
 %0A   
@@ -815,16 +815,33 @@
 i + 1, j
+, processed, memo
 );%0A     
@@ -874,24 +874,41 @@
 (s, i, j - 1
+, processed, memo
 );%0A        i
@@ -945,16 +945,33 @@
 1, j - 1
+, processed, memo
 );%0A     
@@ -977,22 +977,16 @@
     
-return 
 count +
+=
  a +
@@ -993,16 +993,68 @@
  b + c;%0A
+//        memo%5Bi%5D%5Bj%5D = count;%0A        return count;%0A
     %7D%0A%0A 
@@ -1385,16 +1385,18 @@
 m647();%0A
+//
         
@@ -1505,19 +1505,243 @@
 s(%22a
-aa%22)); // 6
+bbc%22)); // 5%0A//        System.out.println(prob.countSubstrings(%22aaa%22)); // 6%0A//        System.out.println(prob.countSubstrings(%22aaabbbccc%22)); // 18%0A        System.out.println(prob.countSubstrings(%22xkjkqlajprjwefilxgpdpebieswu%22)); // 30
 %0A   

Update problem 647