LeetCode-in-All

647. Palindromic Substrings

Medium

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”.

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

Solution

class Solution {
  void expand(List<String> a, int l, int r, List<int> res) {
    while (l >= 0 && r < a.length) {
      if (a[l] != a[r]) {
        return;
      } else {
        res[0]++;
        l--;
        r++;
      }
    }
  }

  int countSubstrings(String s) {
    List<String> a = s.split(''); // Dart's equivalent of `toCharArray()`
    List<int> res = [0]; // Using a list to mimic the behavior of an int array
    for (int i = 0; i < a.length; i++) {
      expand(a, i, i, res);      // Odd length palindrome
      expand(a, i, i + 1, res);  // Even length palindrome
    }
    return res[0];
  }
}

This site is open source. Improve this page.