Skip to content

647. Palindromic Substrings 👍

  • Time: $O(n^2)$
  • Space: $O(1)$
 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
class Solution {
 public:
  int countSubstrings(string s) {
    int ans = 0;

    for (int i = 0; i < s.length(); ++i) {
      ans += extendPalindromes(s, i, i);
      ans += extendPalindromes(s, i, i + 1);
    }

    return ans;
  }

 private:
  int extendPalindromes(const string& s, int l, int r) {
    int count = 0;

    while (l >= 0 && r < s.length() && s[l] == s[r]) {
      ++count;
      --l;
      ++r;
    }

    return count;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int countSubstrings(String s) {
    int ans = 0;

    for (int i = 0; i < s.length(); ++i) {
      ans += extendPalindromes(s, i, i);
      ans += extendPalindromes(s, i, i + 1);
    }

    return ans;
  }

  private int extendPalindromes(final String s, int l, int r) {
    int count = 0;

    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
      ++count;
      --l;
      ++r;
    }

    return count;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def countSubstrings(self, s: str) -> int:
    def extendPalindromes(l: int, r: int) -> int:
      count = 0

      while l >= 0 and r < len(s) and s[l] == s[r]:
        count += 1
        l -= 1
        r += 1

      return count

    ans = 0

    for i in range(len(s)):
      ans += extendPalindromes(i, i)
      ans += extendPalindromes(i, i + 1)

    return ans