9. Palindrome SubStrings

The problem can be found at the following link: Question Link

Problem Description

Given a string s, count all palindromic substrings present in the string where the length of each palindromic substring is greater than or equal to 2.

Examples

Example 1

Input:

s = "abaab"

Output:

3

Explanation: All palindromic substrings are: "aba", "aa", and "baab".

Example 2

Input:

s = "aaa"

Output:

3

Explanation: All palindromic substrings are: "aa", "aa", and "aaa".

Example 3

Input:

s = "abbaeae"

Output:

4

Explanation: All palindromic substrings are: "bb", "abba", "aea", and "eae".

Constraints

  • $( 2 \leq \text{length}(s) \leq 10^3 )$

  • String contains only lowercase English characters.

My Approach

Dynamic Programming (DP) (O(N²) Time, O(N²) Space)

  1. We use a 2D boolean DP array dp[i][j] to indicate whether the substring s[i..j] is a palindrome.

  2. Base cases: Every single character is trivially a palindrome (we won't count single-character palindromes as per problem statement).

  3. We fill the DP table in a manner that checks if the characters at both ends match and if the inside substring is also a palindrome.

  4. Whenever we find dp[i][j] = true and (j - i + 1) >= 2, we increment our palindrome count.

  5. Return the final count of palindromic substrings of length >= 2.

Algorithm Steps

  1. Create a 2D array dp[n][n], initialized to false, where n is the length of s.

  2. Traverse the string in reverse order for the starting index i (from n-1 down to 0).

  3. Set dp[i][i] = true for all i (single-character palindromes, though not counted, are needed to build multi-character palindromes).

  4. For each i, iterate j from i+1 to n-1:

    • If s[i] == s[j] and the substring in-between is a palindrome (or j - i == 1 for adjacent chars), set dp[i][j] = true.

    • If dp[i][j] is true, increment the count.

  5. The result is the total count of palindromic substrings of length ≥ 2.

Time and Auxiliary Space Complexity

  • Expected Time Complexity: O(N²), where N is the length of the string. We have nested loops iterating through the string to fill the DP table.

  • Expected Auxiliary Space Complexity: O(N²), for maintaining the 2D DP table.

Code (C++)

class Solution {
  public:
    int countPS(string& s) {
        int n = s.size(), res = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = true;
            for (int j = i + 1; j < n; ++j)
                if (s[i] == s[j] && (j - i == 1 || dp[i + 1][j - 1]))
                    dp[i][j] = true, res++;
        }
        return res;
    }
};
⚡ Alternative Approaches

1️⃣ Expand Around Center (O(N²) Time, O(1) Space)

Idea:

  • Treat each index (and index gap) as a potential palindrome center.

  • Expand outward while the characters match.

  • Count palindromic substrings of length ≥ 2.

class Solution {
public:
    int countPS(string& s) {
        int n = s.size(), res = 0;
        for (int i = 0; i < n; ++i) {
            for (int l = i, r = i; l >= 0 && r < n && s[l] == s[r]; --l, ++r) res++;
            for (int l = i, r = i + 1; l >= 0 && r < n && s[l] == s[r]; --l, ++r) res++;
        }
        return res - n;
    }
};

🔹 No extra space needed 🔹 Simple to implement

Code (Java)

class Solution {
    public int countPS(String s) {
        int n = s.length(), res = 0;
        for (int i = 0; i < n; i++) {
            for (int l = i, r = i; l >= 0 && r < n && s.charAt(l) == s.charAt(r); l--, r++) res++;
            for (int l = i, r = i + 1; l >= 0 && r < n && s.charAt(l) == s.charAt(r); l--, r++) res++;
        }
        return res - n;
    }
}

Code (Python)

class Solution:
    def countPS(self, s):
        n, res = len(s), 0
        for i in range(n):
            l, r = i, i
            while l >= 0 and r < n and s[l] == s[r]: res += 1; l -= 1; r += 1
            l, r = i, i + 1
            while l >= 0 and r < n and s[l] == s[r]: res += 1; l -= 1; r += 1
        return res - n

2️⃣ Manacher’s Algorithm (O(N) Time, O(N) Space)

Idea:

  • Transform string into a format with separators (e.g., #a#b#a#b#).

  • Use Manacher’s algorithm to find palindromes in O(N).

  • Count palindromes of length ≥ 2 from the computed radius array.

class Solution {
public:
    int countPS(string s) {
        string t = "#";
        for (char c : s) t += c + string("#");
        int n = t.size(), res = 0;
        vector<int> p(n, 0);
        int c = 0, r = 0;

        for (int i = 1; i < n - 1; i++) {
            int mirr = 2 * c - i;
            if (i < r) p[i] = min(r - i, p[mirr]);

            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) {
                c = i;
                r = i + p[i];
            }

            res += (p[i] / 2);
        }

        return res;
    }
};

🔹 Fastest for large N 🔹 Trickier to implement

📊 Comparison of Approaches

Approach

⏱️ Time Complexity

🗂️ Space Complexity

✅ Pros

⚠️ Cons

Dynamic Programming (DP)

🟡 O(N²)

🟡 O(N²)

Reliable and efficient for mid-size N

Requires 2D DP table

Expand Around Center

🟡 O(N²)

🟢 O(1)

Simple and space-efficient

Slower for very large N

Manacher’s Algorithm

🟢 O(N)

🟡 O(N)

Fastest for N > 10⁵

Complex to implement

💡 Best Choice?

  • ✅ For simplicity: Use Expand Around Center.

  • ✅ For optimal runtime on large inputs: Use Manacher’s Algorithm.

  • ✅ For learning DP concepts: Use the Dynamic Programming approach.

Code (Java)

class Solution {
    public int countPS(String s) {
        int n = s.length(), res = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = true;
            for (int j = i + 1; j < n; j++)
                if (s.charAt(i) == s.charAt(j) && (j - i == 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    res++;
                }
        }
        return res;
    }
}

Code (Python)

class Solution:
    def countPS(self, s):
        n, res = len(s), 0
        dp = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = True
            for j in range(i + 1, n):
                if s[i] == s[j] and (j - i == 1 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    res += 1
        return res

Note: Single-character palindromes are not counted as per problem statement. All approaches shown ensure only palindromes of length ≥ 2 are incremented.

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

Previous8. Longest Palindrome in a StringNext10. Edit Distance

Last updated