LC-1930 Medium LeetCode

1930. Unique Length-3 Palindromic Subsequences

Hash Table String Bit Manipulation Prefix Sum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 71% Topics: Hash Table, String, Bit Manipulation, Prefix Sum

Reading material

Arrays & Hashing 12 min Strings 12 min Bit Manipulation 10 min

Reference solution (spoiler · python)

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

class Solution(object):
    def countPalindromicSubsequence(self, s):
        """
        :type s: str
        :rtype: int
        """
        first, last = [len(s)]*26, [-1]*26
        for i, c in enumerate(s):
            first[ord(c)-ord('a')] = min(first[ord(c)-ord('a')], i)
            last[ord(c)-ord('a')] = max(last[ord(c)-ord('a')], i)
        return sum(len(set(s[i] for i in xrange(first[c]+1, last[c]))) for c in xrange(26))

Solution from kamyu104/LeetCode-Solutions · MIT