Palindromic Substrings

January 10, 2025

Palindromic Substrings

Given a string `s`, find and return the total number of sub strings in `s` that are palindromes.

A palindrome is a string that remains the same when read both forward and backward.

TOP 150 NOTOUT QUESTIONS
palindromic substrings problem

Constraints:

  • 1 <= s.length <= 1000
  • “s” consists of lowercase English letters.

Palindromic Substrings Solution

Approaches for solving Palindromic substrings problem

There are mainly 5 approach to solve this problem 

  1. Brute Force Method
  2. Dynamic Programming Method
  3. Two Pointers Method
  4. Two Pointers (Optimal) Method
  5. Manacher’s algorithms

Approach 1 : Brute Force

  • Check every possible substring in the string.
  • For each substring, see if it reads the same forward and backward.
  • This method is simple but slow because it checks all combinations.

Approach 3 : Two Pointers

  • Think of each character (and pair of characters) as the center of a palindrome.
  • Expand outward, checking if characters match, and count all palindromes found.
  • This method is faster and uses less memory.

Approach 5 : Manacher’s Problem

  • Preprocess the string with separators to unify palindrome checks, and maintain an array that tracks the radius of the longest palindrome at each position.
  • Use symmetry to skip redundant checks and expand efficiently.

 

 

Approach 2 : Dynamic Programming

  • Use a table to store if a sub string is a palindrome.
  • Start with small sub strings (length 1 and 2), then use this information to check larger ones.
  • This saves time by reusing results from smaller sub strings.

Approach 4 : Two Pointers (Optimal)

  • Use two pointers to expand around potential centers of palindromes.
  • Treat each character and pair of consecutive characters as centers (to handle odd and even-length palindromes).
  • Expand outward from each center and count valid palindromic substrings.

1. Brute Force Method:

Check all possible substrings in the string and verify each one to see if it is a palindrome. This method is simple but slow because it explores all combinations.

  • Time complexity: O(n^3)
  • Space complexity: O(1)

Code

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;

        for (int i = 0; i < s.size(); i++) {
            for (int j = i; j < s.size(); j++) {
                int l = i, r = j;
                while (l < r && s[l] == s[r]) {
                    l++;
                    r--;
                }
                res += (l >= r);
            }
        }

        return res;
    }
};

2. Dynamic Programming  Method

Use a table to track if sub strings are palindromes, starting with smaller ones and building up to larger ones. This approach reuses previous results to avoid redundant checks.

  • Time complexity: O(n^2)
  • Space complexity: O(n^2)

Code

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0, n = s.length();
        vector> dp(n, vector(n, false));

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && 
                    (j - i <= 2 || dp[i + 1][j - 1])) {

                    dp[i][j] = true;
                    res++;
                }
            }
        }

        return res;
    }
};

3. Two Pointers Method

Expand around each character (or pair of characters) as the center of a potential palindrome. Count all valid palindromes found by comparing characters outward.

  • Time complexity: O(n^2)
  • Space complexity: O(1)

Code

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;

        for (int i = 0; i < s.size(); i++) {
            int l = i, r = i;
            while (l >= 0 && r < s.size() &&
                   s[l] == s[r]) {
                res++;
                l--;
                r++;
            }
            l = i;
            r = i + 1;
            while (l >= 0 && r < s.size() &&
                   s[l] == s[r]) {
                res++;
                l--;
                r++;
            }
        }

        return res;
    }
};

4. Two Pointers (Optimal) Method

Similar to the regular two-pointer method but optimized to handle odd and even-length palindromes efficiently. It avoids unnecessary checks and uses O(1) space.

  • Time complexity: O(n^2)
  • Space complexity: O(1)

Code

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            res += countPali(s, i, i);
            res += countPali(s, i, i + 1);
        }
        return res;
    }

private:
    int countPali(string s, int l, int r) {
        int res = 0;
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            res++;
            l--;
            r++;
        }
        return res;
    }
};

5. Manacher’s Algorithm

This method transforms the string to handle odd and even-length palindromes uniformly by adding separators (e.g., #) between characters. It then uses a center-expansion technique with precomputed symmetry to find all palindromic substrings in O(n) time.

  • Time complexity: O(n)
  • Space complexity: O(n)

Code

class Solution {
public:
    vector<int> manacher(string& s) {
        if (!s.size()) return {};
        string t = "#" + string(1, s[0]);
        for (int i = 1; i < s.size(); ++i)
            t += "#" + string(1, s[i]);
        t += "#";
        int n = t.size();
        vector<int> p(n, 0);
        int l = 0, r = 0;
        for (int i = 0; i < n; i++) {
            p[i] = (i < r) ? min(r - i, p[l + (r - i)]) : 0;
            while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
                   t[i + p[i] + 1] == t[i - p[i] - 1])
                p[i]++;
            if (i + p[i] > r)
                l = i - p[i], r = i + p[i];
        }
        return p;
    }

    int countSubstrings(string s) {
    vector<int> p = manacher(s);
        int res = 0;
        for (int i : p) {
            res += (i + 1) / 2;
        }
        return res;
    }
};

More Articles