1930. Unique Length-3 Palindromic Subsequences

🟧 Medium

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

Example 1

Input: s = "aabca" Output: 3s Explanation: The 3 palindromic subsequences of length 3 are:

• "aba" (subsequence of "aabca")

• "aaa" (subsequence of "aabca")

• "aca" (subsequence of "aabca")

Example 2

Input: s = "bbcbaba" Output: 4 Explanation: The 4 palindromic subsequences of length 3 are:

• "bbb" (subsequence of "bbcbaba")

• "bcb" (subsequence of "bbcbaba")

• "bab" (subsequence of "bbcbaba")

• "aba" (subsequence of "bbcbaba")

Constraints

• 3 <= s.length <= 10^5

• s consists of only lowercase English letters.

Hint 1

What is the maximum number of length-3 palindromic strings?

Hint 2

How can we keep track of the characters that appeared to the left of a given position?

Solution

My Solution

func countPalindromicSubsequence(s string) int {
    firstIdx := make(map[byte]int, len(s))
    lastIdx := make(map[byte]int, len(s))

    for i:=0; i<len(s); i++{
        if _, ok := firstIdx[s[i]]; !ok {
            firstIdx[s[i]]=i
        }

        lastIdx[s[i]]=i
    }

    count := 0

    for char, start := range firstIdx {
        end := lastIdx[char]
        if start < end {
            uniqueChars := make(map[byte]bool, end-start)
            for i:=start+1; i<end; i++ {
                uniqueChars[s[i]]=true
            }

            count+=len(uniqueChars)
        }
    }

    return count
}

result

Leetcode: link