Count Palindromic Substrings

89.Count Palindromic Substrings

String

Two Pointers

Dynamic Programming

Problem Statement:

Given a string s, return the number of palindromic substrings in it. A substring is palindromic if it reads the same forward and backward. Each character in the string is considered a valid palindrome.

Algorithm:

1. Use a helper function to find all palindromes centered at each position in the string.
2. For each character in the string:
• Expand from the center to find all odd-length palindromes.
• Expand from the center between two characters to find all even-length palindromes.
3. Count the number of palindromes found during each expansion.

Complexity:

Time: O(n²), where n is the length of the string | Space: O(1)

Java Implementation:

public class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        // Expand around each character (odd-length palindromes)
        // and between each pair of characters (even-length palindromes)
        for (int i = 0; i < s.length(); i++) {
            count += findPalindromes(s, i, i);     // Odd-length
            count += findPalindromes(s, i, i + 1); // Even-length
        }
        return count;
    }

    // Expand from the center to find all palindromes
    public int findPalindromes(String s, int l, int r) {
        int count = 0;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            count++; // Count the current palindrome
            l--;     // Expand left
            r++;     // Expand right
        }
        return count;
    }
}

Python Implementation:

def countSubstrings(s):
    def findPalindromes(s, l, r):
        count = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1  # Count the current palindrome
            l -= 1      # Expand left
            r += 1      # Expand right
        return count

    count = 0
    for i in range(len(s)):
        count += findPalindromes(s, i, i)      # Odd-length
        count += findPalindromes(s, i, i + 1) # Even-length
    return count

C++ Implementation:

#include 
using namespace std;

class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;
        // Expand around each character (odd-length palindromes)
        // and between each pair of characters (even-length palindromes)
        for (int i = 0; i < s.size(); i++) {
            count += findPalindromes(s, i, i);     // Odd-length
            count += findPalindromes(s, i, i + 1); // Even-length
        }
        return count;
    }

private:
    int findPalindromes(string& s, int l, int r) {
        int count = 0;
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            count++; // Count the current palindrome
            l--;     // Expand left
            r++;     // Expand right
        }
        return count;
    }
};