algoadvance

Leetcode 647. Palindromic Substrings

Problem Statement

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

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: "a", "b", and "c" are palindromic substrings.

Example 2:

Input: s = "aaa"
Output: 6
Explanation: "a", "a", "a", "aa", "aa", and "aaa" are palindromic substrings.

Clarifying Questions

  1. What are the constraints on the input?
    • The length of s will be between 1 and 1000.
    • s consists of only lowercase English letters.
  2. Are there any special characters or spaces in the string?
    • No, the string s will consist solely of lowercase English letters.
  3. Should I count overlapping palindromic substrings separately?
    • Yes, each palindromic substring should be counted.

Strategy

To solve this problem, we can use two main approaches:

  1. Expand Around Center:
    • Every palindrome has a center. The center can be one character (odd-length palindromes) or two consecutive characters (even-length palindromes).
    • We can expand around each possible center and count how many palindromes we get.
  2. Dynamic Programming:
    • Use a 2D table dp where dp[i][j] will be true if the substring s[i:j+1] is a palindrome.
    • Fill this table and count the true values.

For simplicity and efficiency, we will use the Expand Around Center approach.

Implementation in C++

Here’s the code for the Expand Around Center approach:

#include <iostream>
#include <string>

class Solution {
public:
    int countSubstrings(std::string s) {
        int n = s.length();
        int count = 0;
        
        // Helper function to count palindromes around a center.
        auto countPalindromesAroundCenter = [&](int left, int right) {
            while (left >= 0 && right < n && s[left] == s[right]) {
                count++;
                left--;
                right++;
            }
        };
        
        // Expand around each character and each pair.
        for (int i = 0; i < n; i++) {
            countPalindromesAroundCenter(i, i); // Odd length palindromes
            countPalindromesAroundCenter(i, i + 1); // Even length palindromes
        }
        
        return count;
    }
};

int main() {
    Solution sol;
    std::string s1 = "abc";
    std::string s2 = "aaa";
    
    std::cout << "Number of palindromic substrings in " << s1 << " is " << sol.countSubstrings(s1) << std::endl;
    std::cout << "Number of palindromic substrings in " << s2 << " is " << sol.countSubstrings(s2) << std::endl;
    
    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI