Palindromic Substrings

Given a string ( s ), the task is to find the number of palindromic substrings in it. A string is a palindrome if it reads the same backward as forward.

Algorithm

  1. Initialize: Initialize a variable count to store the number of palindromic substrings.

  2. Iterate Through the String: Loop through the string, considering each character as the center of a potential palindrome.

    a. Check Odd Length Palindromes: Check palindromes with an odd length by expanding around the current character as the center. Increment the count for each valid palindrome.

    b. Check Even Length Palindromes: Check palindromes with an even length by expanding around the current character and the next character as the centers. Increment the count for each valid palindrome.

  3. Return: Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def countSubstrings(self, s: str) -> int:
        def expandAroundCenter(left: int, right: int) -> int:
            local_count = 0
            while left >= 0 and right < len(s) and s[left] == s[right]:
                local_count += 1
                left -= 1
                right += 1
            return local_count

        count = 0
        for i in range(len(s)):
            count += expandAroundCenter(i, i)     # Odd length palindromes
            count += expandAroundCenter(i, i + 1) # Even length palindromes

        return count

Explanation

  • We consider each character in the string as a potential center for palindromes.
  • We check for both odd and even length palindromes by expanding around the center.
  • We continue expanding as long as the characters are the same and we are within the bounds of the string.

Insights

  • Time Complexity: ( O(n^2) ), where ( n ) is the length of the string. We iterate through the string, and for each character, we may expand up to ( n/2 ) times.
  • Space Complexity: ( O(1) ), as we only use constant extra space.

This solution efficiently calculates the number of palindromic substrings within the given string by considering both odd and even length palindromes.

=begin

  1. Define the Term Palindrome

    racecar

    r, a, c, e, c, a, r cec aceca racecar

  2. Size is increasing from 1, 2, 3 and so on till the size of the input string

  3. Clues

    • We are taking all possible subtrings and check if it is a palindrome
    • count - counting problem (combinatorics)
    • Exhaustive Search

0 1 2 a a a

  1. Brute Force Approach

    Figure out all combinations of strings, length 1, 2, 3, …. size of the string and check if it is a palindrome.

    T: O(N^2) + O(N) , O(N^3), T: O(N^2*K) S: O(1)

    T: O(N^2)

    Identify the unnecessary work.

    • We can remove the inner for loop.
    • Remove the palindrome check altogether

    f(n) = f(n-1) + f(n-2) i 0 1 2 3 4 5 a b c d e f j

Repeated work in brute force Optimal Subtructure - Using the string racecar we saw how the bigger strings can use the smaller strings’ answers to figure if they are palindrome or not

Overlapping Subproblems It is easier to see the overlapping subproblems in the recursion tree

  • Unit of decomposition Do we reduce it by 1, 2, half the size of the input or some other constant factor? Do you see a self similar problem? A smaller instance of the original problem.

    Size of the input is 3 0, 1, 2

  • Identify the state (Identify the variables) i, j

    f(i, j) = f(i+1, j-1) && s[i] == s[j] if size > 2 = true if size == 1 = true if size == 2 && s[i] == s[j]

  1. All the cells in the 2D dp table that has the value of i == j (0,0), (1,1), (2,2) Put either 1 or true

    (0,1), (1,2), (2,3) Put either 1 or true if s[i] == s[j]

    (0,2), inner string (1, 1)

  2. How do we use the dp table we filled out using the recurrence relation to calculate the ouput? Output will be equal to the number of true in the dp table.

Time: O(N^2) Space: O(N^2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# @param {String} s
# @return {Integer}
def count_substrings(s)
  n = s.size
  count = 0

    if n == 0
        return 0
    end
 
    dp = Array.new(n) { Array.new(n, false) }

    for i in (0..n-1)
       dp[i][i] = true
        count += 1
    end
    for i in (0..n-1)
        same = (s[i] == s[i+1])
       dp[i][i+1] = same

       if same
           count += 1
       end 
    end

    for length in (3..n)
       i = 0
       j = i + length - 1
        loop do
            break if j == n

            dp[i][j] = dp[i+1][j-1] && s[i] == s[j]

            if dp[i][j]
                count += 1
            end
            i += 1
            j += 1
        end
    end

    return count
end