Java

/**

 Given a string, your task is to count how many palindromic substrings in this string.

 The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

 Example 1:

 Input: "abc"
 Output: 3
 Explanation: Three palindromic strings: "a", "b", "c".


 Example 2:

 Input: "aaa"
 Output: 6
 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".


 Note:

 The input string length won't exceed 1000.

 */

public class Palindromic_Substrings {

    public static void main (String[] args) {
        Palindromic_Substrings out = new Palindromic_Substrings();
        Solution s = out.new Solution();

        System.out.println(s.countSubstrings("aaaaa")); // 15
    }

    class Solution {
        public int countSubstrings(String s) {

            int count = 0;

            // dp[i][j] meaning i-th char to j-th char
            boolean[][] dp = new boolean[s.length()][s.length()];

            for (int i = 0; i < dp.length; i++) {
                dp[i][i] = true;
                count++;
            }

            // @note: below issue is same direction, aaaa case, 1-st and 4th is valid but not counted
//            for (int i = 0; i < s.length(); i++) {
//                for (int j = i + 1; j < s.length(); j++) {
//                    if (j - i == 1) { // case:  "aa"
//                        if (s.charAt(i) == s.charAt(j)) {
//                            dp[i][j] = true;
//                            count++;
//                        }
//                    } else {
//                        if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
//                            dp[i][j] = true;
//                            count++;
//                        }
//                    }
//                }
//            }

            // from right to left
            for (int i = s.length() - 1; i >= 0; i--) {
                for (int j = i + 1; j < s.length(); j++) {
                    if (j - i == 1) { // case:  "aa"
                        if (s.charAt(i) == s.charAt(j)) {
                            dp[i][j] = true;
                            count++;
                        }
                    } else {
                        if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                            dp[i][j] = true;
                            count++;
                        }
                    }
                }
            }

            return count;
        }
    }


    class Solution222 {
        public int countSubstrings(String s) {
            int count = 0;

            // dp[i][j] meaning i-th char to j-th char
            boolean[][] dp = new boolean[s.length()][s.length()];

            for (int i = 0; i < dp.length; i++) {
                dp[i][i] = true;
                count++;
            }

            // from left to right
            for (int i = 0; i < s.length(); i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (i - j == 1) { // case:  "aa"
                        if (s.charAt(i) == s.charAt(j)) {
                            dp[j][i] = true;
                            count++;
                        }
                    } else {
                        if (s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1]) {
                            dp[j][i] = true;
                            count++;
                        }
                    }
                }
            }

            return count;
        }
    }
}

Java

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            count++;
            int maxLength = Math.min(i, length - 1 - i);
            for (int j = 1; j <= maxLength; j++) {
                if (s.charAt(i - j) == s.charAt(i + j))
                    count++;
                else
                    break;
            }
        }
        for (int i = 1; i < length; i++) {
            int left = i - 1, right = i;
            if (s.charAt(left) != s.charAt(right))
                continue;
            count++;
            int maxLength = Math.min(left, length - 1 - right);
            for (int j = 1; j <= maxLength; j++) {
                if (s.charAt(left - j) == s.charAt(right + j))
                    count++;
                else
                    break;
            }
        }
        return count;
    }
}

All Problems

All Solutions