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: Three palindromic substrings: "a", "b", "c".

Example 2:

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

Clarifying Questions

  1. Input Constraints:
    • What is the length range of string s?
    • Are we dealing with ASCII, Unicode, or some restricted character set?
  2. Output Validation:
    • Should the function print the result or return it?

Once these are clarified, we can move forward with the implementation.

Assuming the string length can be up to 1000 as typical in LeetCode problems and contains only lowercase ASCII characters. The function should return the result and not print it.

Strategy

We can solve this problem using a dynamic programming approach or a more efficient center expansion approach.

Center Expansion Approach

  1. Palindromes can be centered around 1 character or 2 characters.
  2. For each character in the string, consider it as the center of a palindrome and try to expand outwards as long as the substring is a palindrome.
  3. Count each palindrome found in the process.

This method ensures that we check all possible palindromic substrings efficiently.

Code

Here is the Java implementation of the center expansion approach:

public class Solution {
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
        
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            // Odd length palindromes
            count += expandAroundCenter(s, i, i);
            // Even length palindromes
            count += expandAroundCenter(s, i, i + 1);
        }
        
        return count;
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

Time Complexity

The center expansion approach has a time complexity of (O(n^2)):

So, overall time complexity: (O(n) * O(n) = O(n^2))

This approach is both time-efficient and straightforward to implement for the given problem.

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