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;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/palindromic-substrings/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        int countSubstrings(string s) {
            int N = s.size(), ans = N; // initially all the single characters are counted
            for (int i = 0; i < N; ++i) { // odd length
                for (int j = 1; i - j >= 0 && i + j < N && s[i - j] == s[i + j]; ++j) ++ans;
            }
            for (int i = 1; i < N; ++i) { // even length
                for (int j = 0; i - j - 1 >= 0 && i + j < N && s[i - j - 1] == s[i + j]; ++j) ++ans;
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        ans = 0
        for i in range(n):
          left = right = i
          while left >= 0 and right < n and s[left] == s[right]:
            ans += 1
            left -= 1
            right += 1
    
          left = i
          right = i + 1
          while left >= 0 and right < n and s[left] == s[right]:
            ans += 1
            left -= 1
            right += 1
        return ans
    
    

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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/palindromic-substrings/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        int countSubstrings(string s) {
            int N = s.size(), ans = N; // initially all the single characters are counted
            for (int i = 0; i < N; ++i) { // odd length
                for (int j = 1; i - j >= 0 && i + j < N && s[i - j] == s[i + j]; ++j) ++ans;
            }
            for (int i = 1; i < N; ++i) { // even length
                for (int j = 0; i - j - 1 >= 0 && i + j < N && s[i - j - 1] == s[i + j]; ++j) ++ans;
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        ans = 0
        for i in range(n):
          left = right = i
          while left >= 0 and right < n and s[left] == s[right]:
            ans += 1
            left -= 1
            right += 1
    
          left = i
          right = i + 1
          while left >= 0 and right < n and s[left] == s[right]:
            ans += 1
            left -= 1
            right += 1
        return ans
    
    

All Problems

All Solutions