Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

647. Palindromic Substrings

Time: $O(n^2)$

Space: $O(1)$

			


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;
  }
};




			


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;
  }
}




			


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