unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 647: Palindromic Substrings

link

We can check if a string is a palindrome in two ways:

  1. Inwards from the two ends
  2. Outwards from center

Both ways take \mathcal{O}(n) time. However, there is a difference: the count of possible pairs of end points is \mathcal{O}\left({n}\choose{2}\right) = \mathcal{O}(n^2) whereas the count of possible centers is \mathcal{O}(n).

Process inwards from two ends

Brute force

Try all possible substrings.

Time: \mathcal{O}(n^3), space: \mathcal{O}(1).

class Solution:
    def countSubstrings(self, s: str) -> int:
        def is_palindrome(s: str, l: int, r: int) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l, r = l+1, r-1
            return True
        
        n = len(s)
        count = 0
        for start in range(n):
            for end in range(start, n):
                count += (1 if is_palindrome(s, start, end) else 0)
        return count

Dynamic programming

Using DP, for all possible substrings, we can compute if it is a palindrome in total \mathcal{O}(n^2) time. Counting can piggyback on it.

Subproblem

Let P(i, j) denote if the substring s[i:j+1] is a palindrome. Then:

P(i, j) = \begin{cases} \texttt{true}, & \text{if } i < j \\ P(i+1, j-1), & \text{if } s[i] = s[j] \\ \texttt{false} & \text{otherwise} \end{cases}

Order

Size of a subproblem is (j-i+1), processing them in the order of increasing size gives a topological order.

Time: \mathcal{O}(n^2), space: \mathcal{O}(n^2).

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        count = n

        for sz in range(2, n + 1):
            for i in range(0, n - sz + 1):
                j = i + sz - 1
                dp[i][j] = (s[i] == s[j]) and (dp[i + 1][j - 1] if i + 2 <= j else True)
                count += (1 if dp[i][j] else 0)

        return count

Process outwards from center

Brute force

Time: \mathcal{O}(n^2), space: \mathcal{O}(1).

class Solution:
    def countSubstrings(self, s: str) -> int:
        def count_palindromes(s: str, left: int, right: int):
            n = len(s)
            count = 0
            while left >= 0 and right < n:
                if s[left] != s[right]:
                    break
                count, left, right = count+1, left-1, right+1
            return count

        n = len(s)
        count = n
        for c in range(n):
            count += count_palindromes(s, c-1, c+1)
            count += count_palindromes(s, c,   c+1)
        return count

tanvirdotzaman

,

Leave a comment