Palindromic Substrings medium

Problem Statement

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

A substring is a contiguous sequence of characters within a 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

The core idea is to iterate through the string and for each character, check for palindromes expanding outwards:

1. Initialization: Create a counter count to store the number of palindromic substrings, initialized to 0.

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

3. Odd Length Palindromes: For each character, consider it as the center of a potential odd-length palindrome. Expand outwards from the center, checking if the characters at positions i-k and i+k are equal. Increment k until you find unequal characters or reach the string boundaries. Increment count for each palindrome found.

4. Even Length Palindromes: For each character (except the last), consider the characters at positions i and i+1 as the center of a potential even-length palindrome. Expand outwards from this center, checking if the characters at positions i-k and i+k+1 are equal. Increment k until you find unequal characters or reach the string boundaries. Increment count for each palindrome found.

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

Explanation

The algorithm efficiently checks for all possible palindromic substrings without redundant checks. By expanding outwards from the center of potential palindromes (both odd and even lengths), we ensure that every palindrome is counted exactly once. The use of two nested loops ensures that all possible centers and expansions are considered.

Code

def countSubstrings(s):
    """
    Counts the number of palindromic substrings in a given string.

    Args:
        s: The input string.

    Returns:
        The number of palindromic substrings.
    """
    n = len(s)
    count = 0
    for i in range(n):
        # Odd length palindromes
        l, r = i, i
        while l >= 0 and r < n and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1

        # Even length palindromes
        l, r = i, i + 1
        while l >= 0 and r < n and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1

    return count

Complexity

• Time Complexity: O(n^2), where n is the length of the string. This is because we have nested loops that iterate through all possible centers and expansions of palindromes.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.