Blind 75 - problem 19 : Palindromic Substrings

Palindromic Substrings - LeetCode Solution & Explanation

Problem Statement

Given a string s, return the number of palindromic substrings in s.

A substring is a contiguous sequence of characters within a string.
A palindrome is a string that reads the same forward and backward.

Constraints

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

Example 1

Input: s = "abc"
Output: 3
Explanation: Each character is a palindrome ("a", "b", "c").

Example 2

Input: s = "aaa"
Output: 6
Explanation: Palindromic substrings are ("a", "a", "a", "aa", "aa", "aaa").

---

Optimal Approach: Expand Around Center

Key Idea:

Each single character and every pair of adjacent characters in s can be the center of a potential palindrome.

We expand outward from each center to check for longer palindromes.

Steps:

1. Iterate through the string:
   • Expand odd-length palindromes (centered on one character).
   • Expand even-length palindromes (centered between two characters).
2. Count all valid palindromes.

Time Complexity: O(n²)

Space Complexity: O(1)

---

LeetCode-Compatible C++ Solution

class Solution {
public:
    int expandAroundCenter(string& s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }
    
    int countSubstrings(string s) {
        int totalCount = 0;
        for (int i = 0; i < s.length(); i++) {
            // Odd-length palindromes
            totalCount += expandAroundCenter(s, i, i);
            // Even-length palindromes
            totalCount += expandAroundCenter(s, i, i + 1);
        }
        return totalCount;
    }
};

---

Step-by-Step Explanation

1. Expand Around Center:
   • For each character i, count palindromes:
     • Centered at i (odd-length).
     • Centered between i and i+1 (even-length).
2. Use a Helper Function:
   • Expands outward while the substring remains a palindrome.
   • Counts each valid palindrome.
3. Total Count is returned.

---

Dry Run (Execution Steps)

Let's take s = "aaa":

Step 1: Checking each character

Index	Odd-length Expansion	Even-length Expansion	Total Count
i = 0	"a" (1)	"aa" (1)	2
i = 1	"a", "aaa" (2)	"aa" (1)	5
i = 2	"a" (1)	"" (0)	6

Final Output: 6

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Check all substrings)	O(n³)	O(1)	Too slow for n = 1000
Dynamic Programming (DP Table)	O(n²)	O(n²)	Uses extra memory
Expand Around Center (Best)	O(n²)	O(1)	Efficient & no extra memory

---

Best Solution & Why?

The Expand Around Center approach is the best because:
✅ O(n²) Time Complexity – Handles n=1000 efficiently.
✅ O(1) Space Complexity – No extra DP table needed.
✅ Simple & Elegant Code – Easy to implement with a helper function.

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute Force (All Substrings)	O(n³)	O(1)
Dynamic Programming (DP Table)	O(n²)	O(n²)
Expand Around Center (Best)	O(n²)	O(1)

---

Conclusion

• Best Approach: Expand Around Center (O(n²) time, O(1) space).
• Why? Avoids recursion, extra memory, and handles large inputs efficiently.
• Similar Problems to Practice:
  1. Longest Palindromic Substring LeetCode #5
  2. Palindrome Partitioning LeetCode #131
  3. Valid Palindrome LeetCode #125