Solution by awice


  • 0

    Approach #1: Brute Force [Time Limit Exceeded]

    Intuition and Algorithm

    For each substring S[i: j+1], let's check if it is a palindrome. If it is, we increment 1 to our answer.

    To check whether a substring S[i: j+1] is a palindrome, we check whether every i+d-th character equals the corresponding j-d-th character, for d up to half the length of the substring.

    Notably, our brute force method avoids creating new substrings which would use unnecessary space.

    Python

    class Solution(object):
        def countSubstrings(self, S):
            def is_palindrome(i, j):
                #Is S[i: j+1] a palindrome?
                for d in range((j-i)/2 + 1):
                    if S[i+d] != S[j-d]:
                        return False
                return True
    
            ans = 0
            for i in range(len(S)):
                for j in range(i, len(S)):
                    if is_palindrome(i, j):
                        ans += 1
            return ans
    

    Complexity Analysis

    • Time Complexity: $$O(N^3)$$, where $$N$$ is the length of the string. After our for i, j loops of complexity $$O(N^2)$$, we spend $$O(N)$$ work to check whether S[i: j+1] is a palindrome.

    • Space Complexity: We need $$O(1)$$ additional space to store the answer.


    Approach #2: Center Expansion [Accepted]

    Intuition

    Every palindrome has a unique center position. For each possible center, we determine all the palindromes that could have that center by scanning from left to right.

    Algorithm

    Let N = len(S). There are 2N-1 possible centers for the palindrome: we could have a center at S[0], between S[0] and S[1], at S[1], between S[1] and S[2], at S[2], etc.

    To iterate over each of the 2N-1 centers, we will move the left pointer every 2 times, and the right pointer every 2 times starting with the second (index 1). Hence, left = center / 2, right = center / 2 + center % 2.

    From here, finding every palindrome starting with that center is straightforward: while the ends are valid and have equal characters, record the answer and expand.

    Python

    def countSubstrings(self, S):
        ans = 0
        for center in range(2 * len(S) - 1):
            left = center // 2
            right = left + center % 2
            while left >= 0 and right < len(S) and S[left] == S[right]:
                ans += 1
                left -= 1
                right += 1
        return ans
    

    Complexity Analysis

    • Time Complexity: $$O(N^2)$$, where $$N$$ is the length of the string. For each center, we could expand potentially up to the bounds of the string. Thus, both the outer loop and the inner loop have $$O(N)$$ complexity.

    • Space Complexity: We need $$O(1)$$ additional space to store the answer.


    Approach #3: Manacher's Algorithm [Accepted]

    Intuition

    If we knew Manacher's algorithm, a linear time algorithm for determining Z[i], the longest half-length of a palindrome with center i, then computing the number of palindromes would simply be sum((z + 1) // 2 for z in Z).

    Algorithm

    We focus on an explanation of Manacher's algorithm.

    To make our implementation easier, we will add '#' characters, between each character of S. We also add a '@' and '$' characters to the beginning and end of S, to form a working string A. We assume these characters do not exist originally in S. The problem of finding the longest palindrome at a given center is the same for string S as it is for A, so this transformation is justified.

    From here on, our position indices will always be in terms of "half indices", represented as full indices in A. Our loop invariants will be that center, right is our knowledge of the palindrome with the largest right-most boundary with center < i, centered at center with right-boundary right. Also, i > center, and we've already computed all Z[j]'s for j < i.

    When i < right, we reflect i about center to be at some coordinate j = 2 * center - i. Then, limited to the interval with radius right - i and center i, the situation for Z[i] is the same as for Z[j].

    For example, if at some time center = 7, right = 13, i = 10, then for a string like A = '@#A#B#A#A#B#A#$', the center is at the '#' between the two middle 'A''s, the right boundary is at the last '#', i is at the last 'B', and j is at the first 'B'.

    Notice that limited to the interval [center - (right - center), right] (the interval with center center and right-boundary right), the situation for i and j is a reflection of something we have already computed. Since we already know Z[j] = 3, we can quickly find Z[i] = min(right - i, Z[j]) = 3.

    Beyond that interval, we can manually expand the palindrome at interval [i - Z[i], i + Z[i]] (centered at i with radius Z[i]) while appropriate. After, we update our knowledge of the palindrome with the largest right-boundary if appropriate.

    Python

    def countSubstrings(self, S):
        def manachers(S):
            A = '@#' + '#'.join(S) + '#$'
            Z = [0] * len(A)
            center = right = 0
            for i in range(1, len(A) - 1):
                if i < right:
                    Z[i] = min(right - i, Z[2 * center - i])
                while A[i - Z[i] - 1] == A[i + Z[i] + 1]:
                    Z[i] += 1
                if i + Z[i] > right:
                    center, right = i, i + Z[i]
            return Z
    
        return sum((v+1)//2 for v in manachers(S))
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the length of the string. The outer loop for i in range(...) is $$O(N)$$. The while loop only checks the condition more than once when Z[i] = right - i. In that case, for each time Z[i] += 1, it increments right. As right can only be incremented up to 2*N+2 times, in total the algorithm is $$O(N)$$.

    • Space Complexity: We used $$O(N)$$ additional space to store A and Z.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.