Leetcode 647 Palindromic Substrings

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.

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

• Bu soruda bize bir string veriliyor ve bu string için palindrome şeklinde kaç farklı alt küme olduğu soruluyor.
• Palindrome önden de ve arkadan da okunduğunda aynı olan kelimeler.
• s = “aaa” için"a", “a”, “a”, “aa”, “aa”, “aaa” alt kümeleri bulunabilir.
• Burada izleyeceğimiz yol her harfi ortadaki harfmiş şekilde kabul ederek 2 işaretçimizi sağa ve sola ilerletmek.
• s = “aaa” için ilk harf olan “a” yı orta kabul ederiz işaretçileri 0. indekse koyarız.İlk palindrome “a” buluruz.İşaretçileri sağa ve sola 1 kaydırırız.0. indeksin solunda bir değer olmadığı için 1. indekse geçeriz.
• “aaa” indeks 1 de ilk palindrome yine “a” oldu işaretçileri sağa ve sola 1 değer kaydırırsak ve bunların eşit olduğunu görürsek 2. palindrome bulduk “aaa”.Bu şekilde tüm stringi tararız.

• Ancak bu yöntem ile sadece 1,3,5 gibi tek sayılı kümeleri bulabiliriz.
• Çift haneli kümeleri bulabilmemiz için “aaa” için sol indeksi i , sağ indeksi i+1 şeklinde almalıyız.

class Solution:
    def countSubstrings(self, s: str) -> int:
        
        res = 0
        
        for i in range(len(s)):
            res += self.countPali(s,i,i)
            res += self.countPali(s,i,i+1)
        return res
    
    def countPali(self,s,l,r):
        res = 0
        while l >= 0 and r<len(s) and s[l] == s[r]:
            res += 1
            l -= 1
            r +=1
        return res