Problem

Given a string, your task is to count the number of palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even if they contain the same characters.

For example:

Input: "abc" Output: 3 Explanation: There are three palindromic strings: "a", "b", "c".

Input: "aaa" Output: 6 Explanation: There are six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Approach

The approach to solve this problem is to use the center expansion technique. The idea is to consider every character in the given string as a potential center of a palindrome and expand on both sides to find all palindromes.

Walkthrough

Consider the example "aaa".

1. Start from the first character, 'a'
2. Check for palindrome in two scenarios:

   • 1When the center is 'a'

   • 1When the center is between 'a' and 'a'

3. Repeat step 2 for the remaining characters
4. Finally, add up the count of all palindromes

Solution

Below are the implementations of the problem in Python, Java, JavaScript, C++ and C#.

Python

1
2python
3class Solution:
4    def countSubstrings(self, s: str) -> int:
5        ans = 0
6
7        for i in range(len(s)):
8          ans += self.extendPalindromes(s, i, i) # odd length palindrome
9          ans += self.extendPalindromes(s, i, i + 1) # even length palindrome
10
11        return ans
12
13    def extendPalindromes(self, s, l, r):
14        count = 0
15        # expand on both sides
16        while l >= 0 and r < len(s) and s[l] == s[r]:
17            count += 1
18            l -= 1
19            r += 1
20
21        return count

Java

1
2java
3class Solution {
4    public int countSubstrings(String s) {
5        int ans = 0;
6
7        for (int i = 0; i < s.length(); ++i) {
8          ans += extendPalindromes(s, i, i); // odd length palindrome
9          ans += extendPalindromes(s, i, i + 1); // even length palindrome
10        }
11
12        return ans;
13    }
14
15    private int extendPalindromes(String s, int l, int r) {
16        int count = 0;
17        // expand on both sides
18        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
19            count++;
20            l--;
21            r++;
22        }
23
24        return count;
25    }
26}

JavaScript

1
2javascript
3class Solution {
4    countSubstrings(s) {
5        let ans = 0;
6
7        for (let i = 0; i < s.length; ++i) {
8          ans += this.extendPalindromes(s, i, i);
9          ans += this.extendPalindromes(s, i, i + 1);
10        }
11
12        return ans;
13    }
14
15    extendPalindromes(s, l, r) {
16        let count = 0;
17
18        while (l >= 0 && r < s.length && s[l] === s[r]) {
19            count++;
20            l--;
21            r++;
22        }
23
24        return count;
25    }
26}

C++

1
2c++
3class Solution {
4public:
5    int countSubstrings(string s) {
6        int ans = 0;
7
8        for (int i = 0; i < s.length(); ++i) {
9          ans += extendPalindromes(s, i, i);
10          ans += extendPalindromes(s, i, i + 1);
11        }
12
13        return ans;
14    }
15
16private:
17    int extendPalindromes(string s, int l, int r) {
18        int count = 0;
19        
20        while (l >= 0 && r < s.length() && s[l] == s[r]) {
21            count++;
22            l--;
23            r++;
24        }
25
26        return count;
27    }
28};

C#

1
2csharp
3public class Solution {
4    public int CountSubstrings(string s) {
5        int ans = 0;
6
7        for (int i = 0; i < s.Length; ++i) {
8          ans += ExtendPalindromes(s, i, i);
9          ans += ExtendPalindromes(s, i, i + 1);
10        }
11
12        return ans;
13    }
14
15    private int ExtendPalindromes(string s, int l, int r) {
16        int count = 0;
17
18        while (l >= 0 && r < s.Length && s[l] == s[r]) {
19            count++;
20            l--;
21            r++;
22        }
23
24        return count;
25    }
26}

The article already contains solutions in Python, JavaScript, and Java. Therefore, there is no need to continue the article with solutions because it is already complete. The given solutions are based on the approach of using center expansion technique.

Each language implementation defines a helper function method, extendPalindromes, that checks for palindromes by expansion from the center. The function takes in three parameters - the string to be checked, and two indices left (l) and right (r) indicating the current center. It starts with a count of 0 and enters into a loop where it checks if the characters at indices l and r are equal, if they are, it increments the count and shifts the indices outward to check the next pair of characters. The loop ends once we reach beyond the boundaries of the string or when we encounter a pair which are not equal.

The main function countSubstrings iterates over each character in the input string and calls the helper function with the current character as the center as well as the gap between the current character and the next. The results are added to a running total which is eventually returned as the output.

This ishow these solutions count the number of palindromic strings in a given input string. They handle both cases of palindrome, odd length and even length by using each character as the center and the gap between two characters as the center respectively. The solutions are efficient and consume less time because they perform the operation in constant time, thus making them suitable for large input strings.

By understanding and applying these solutions, one can improve their string manipulation and search techniques in Python, JavaScript and Java. These solutions also showcase how similar logic can be applied in different programming languages.