LC-2472 Hard LeetCode

2472. Maximum Number of Non-overlapping Palindrome Substrings

Two Pointers String Dynamic Programming Greedy

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 41% Topics: Two Pointers, String, Dynamic Programming, Greedy

Reading material

Two Pointers 9 min Strings 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n * k)
# Space: O(1)

# two pointers, greedy
class Solution(object):
    def maxPalindromes(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        result = prev = 0
        for mid in xrange(2*len(s)-1):
            left, right = mid//2, mid//2+mid%2
            while left >= prev and right < len(s) and s[left] == s[right]:
                if right-left+1 >= k:
                    prev = right+1
                    result += 1
                    break
                left, right = left-1, right+1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT