Welcome to Subscribe On Youtube

647. Palindromic Substrings

Description

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.

Solutions

• Java
• C++
• Python
• Go
• Javascript

• class Solution {
      public int countSubstrings(String s) {
          StringBuilder sb = new StringBuilder("^#");
          for (char ch : s.toCharArray()) {
              sb.append(ch).append('#');
          }
          String t = sb.append('$').toString();
          int n = t.length();
          int[] p = new int[n];
          int pos = 0, maxRight = 0;
          int ans = 0;
          for (int i = 1; i < n - 1; i++) {
              p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * pos - i]) : 1;
              while (t.charAt(i - p[i]) == t.charAt(i + p[i])) {
                  p[i]++;
              }
              if (i + p[i] > maxRight) {
                  maxRight = i + p[i];
                  pos = i;
              }
              ans += p[i] / 2;
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      int countSubstrings(string s) {
          int ans = 0;
          int n = s.size();
          for (int k = 0; k < n * 2 - 1; ++k) {
              int i = k / 2, j = (k + 1) / 2;
              while (~i && j < n && s[i] == s[j]) {
                  ++ans;
                  --i;
                  ++j;
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def countSubstrings(self, s: str) -> int:
          t = '^#' + '#'.join(s) + '#$'
          n = len(t)
          p = [0 for _ in range(n)]
          pos, maxRight = 0, 0
          ans = 0
          for i in range(1, n - 1):
              p[i] = min(maxRight - i, p[2 * pos - i]) if maxRight > i else 1
              while t[i - p[i]] == t[i + p[i]]:
                  p[i] += 1
              if i + p[i] > maxRight:
                  maxRight = i + p[i]
                  pos = i
              ans += p[i] // 2
          return ans
  
  

• func countSubstrings(s string) int {
  	ans, n := 0, len(s)
  	for k := 0; k < n*2-1; k++ {
  		i, j := k/2, (k+1)/2
  		for i >= 0 && j < n && s[i] == s[j] {
  			ans++
  			i, j = i-1, j+1
  		}
  	}
  	return ans
  }
  

• /**
   * @param {string} s
   * @return {number}
   */
  var countSubstrings = function (s) {
      let ans = 0;
      const n = s.length;
      for (let k = 0; k < n * 2 - 1; ++k) {
          let i = k >> 1;
          let j = (k + 1) >> 1;
          while (~i && j < n && s[i] == s[j]) {
              ++ans;
              --i;
              ++j;
          }
      }
      return ans;
  };
  
  

All Problems

All Solutions