palindromic_substrings

View Source

 1# @leet start
 2class Solution:
 3    def countSubstrings(self, s: str) -> int:
 4        """
 5        This question asks us to count the number of palindromic substrings
 6        We can do this by counting the even and odd length palindromes starting
 7        from a given index, and repeat that for all the indexes in the string.
 8        If we can expand a palindrome and its left and right pointers are the
 9        same, we know we've found a new palindrome, and can increment the count.
10        """
11        n = len(s)
12        count = 0
13
14        def expand(l, r):
15            nonlocal n, count
16            while l >= 0 and r < n and s[l] == s[r]:
17                count += 1
18                l -= 1
19                r += 1
20
21        for i in range(n):
22            expand(i, i)
23            expand(i, i + 1)
24
25        return count
26
27
28# @leet end
29
30
31def test():
32    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def countSubstrings(self, s: str) -> int:
 5        """
 6        This question asks us to count the number of palindromic substrings
 7        We can do this by counting the even and odd length palindromes starting
 8        from a given index, and repeat that for all the indexes in the string.
 9        If we can expand a palindrome and its left and right pointers are the
10        same, we know we've found a new palindrome, and can increment the count.
11        """
12        n = len(s)
13        count = 0
14
15        def expand(l, r):
16            nonlocal n, count
17            while l >= 0 and r < n and s[l] == s[r]:
18                count += 1
19                l -= 1
20                r += 1
21
22        for i in range(n):
23            expand(i, i)
24            expand(i, i + 1)
25
26        return count

def countSubstrings(self, s: str) -> int: View Source

 4    def countSubstrings(self, s: str) -> int:
 5        """
 6        This question asks us to count the number of palindromic substrings
 7        We can do this by counting the even and odd length palindromes starting
 8        from a given index, and repeat that for all the indexes in the string.
 9        If we can expand a palindrome and its left and right pointers are the
10        same, we know we've found a new palindrome, and can increment the count.
11        """
12        n = len(s)
13        count = 0
14
15        def expand(l, r):
16            nonlocal n, count
17            while l >= 0 and r < n and s[l] == s[r]:
18                count += 1
19                l -= 1
20                r += 1
21
22        for i in range(n):
23            expand(i, i)
24            expand(i, i + 1)
25
26        return count

This question asks us to count the number of palindromic substrings We can do this by counting the even and odd length palindromes starting from a given index, and repeat that for all the indexes in the string. If we can expand a palindrome and its left and right pointers are the same, we know we've found a new palindrome, and can increment the count.

def test(): View Source

32def test():
33    assert 2 + 2 == 4