Palindromic Substrings medium

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 strings: "a", "b", "c".

Example 2:

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

Steps

1. Initialization: Create a variable count to store the number of palindromic substrings, initializing it to 0.

2. Iteration: Iterate through each character of the string s using a for loop.

3. Palindrome Check (Odd Length): For each character, consider it as the center of a potential odd-length palindrome. Expand outwards from the center, checking if the characters at the left and right are equal. Increment count for each palindrome found.

4. Palindrome Check (Even Length): For each character (except the last), consider the pair of characters centered between it and the next character as the potential center of an even-length palindrome. Expand outwards, checking if the characters are equal. Increment count for each palindrome found.

5. Return: After iterating through all characters, return the final value of count.

Explanation

The solution uses a technique called expand around center. Instead of checking every possible substring, we efficiently check only those substrings that could potentially be palindromes. We do this by considering each character (and each pair of adjacent characters) as the center of a palindrome and expanding outwards to check for symmetry. This avoids redundant checks.

Code

function countSubstrings(s: string): number {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        // Odd length palindromes
        let l = i, r = i;
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            count++;
            l--;
            r++;
        }

        // Even length palindromes
        l = i, r = i + 1;
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            count++;
            l--;
            r++;
        }
    }
    return count;
};

Complexity

• Time Complexity: O(n^2), where n is the length of the string. In the worst case (e.g., "aaaaa"), we might check almost all possible substrings.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input string size.