Skip to content

1930. Unique Length-3 Palindromic Subsequences

Description

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: 3
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 = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

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 <= 105
  • s consists of only lowercase English letters.

Solutions

Solution 1: Enumerate Both End Characters + Hash Table

Thinking

A length-\(3\) palindromic subsequence has the form \(c\_c\). Enumerating triples is impossible for \(n\le 10^5\).

There are only \(26\) letters, so we enumerate the two ends. For a fixed \(c\), the number of distinct characters strictly between its first and last occurrence is the number of distinct palindromes with those ends.

\(\texttt{find}/\texttt{rfind}\) locate the ends and a set counts the middle, in \(O(n|\Sigma|)\) time.

Since the string contains only lowercase letters, we can directly enumerate all pairs of end characters. For each pair of end characters \(c\), we find their first and last occurrence positions \(l\) and \(r\) in the string. If \(r - l > 1\), it means we have found a palindromic subsequence that meets the conditions. We then count the number of unique characters between \([l+1,..r-1]\), which gives the number of palindromic subsequences with \(c\) as the end characters, and add it to the answer.

After enumerating all pairs, we get the answer.

The time complexity is \(O(n \times |\Sigma|)\), where \(n\) is the length of the string and \(\Sigma\) is the size of the character set. In this problem, \(|\Sigma| = 26\). The space complexity is \(O(|\Sigma|)\) or \(O(1)\).

1
2
3
4
5
6
7
8
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        ans = 0
        for c in ascii_lowercase:
            l, r = s.find(c), s.rfind(c)
            if r - l > 1:
                ans += len(set(s[l + 1 : r]))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int countPalindromicSubsequence(String s) {
        int ans = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.indexOf(c), r = s.lastIndexOf(c);
            int mask = 0;
            for (int i = l + 1; i < r; ++i) {
                int j = s.charAt(i) - 'a';
                if ((mask >> j & 1) == 0) {
                    mask |= 1 << j;
                    ++ans;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int ans = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.find_first_of(c), r = s.find_last_of(c);
            int mask = 0;
            for (int i = l + 1; i < r; ++i) {
                int j = s[i] - 'a';
                if (mask >> j & 1 ^ 1) {
                    mask |= 1 << j;
                    ++ans;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func countPalindromicSubsequence(s string) (ans int) {
    for c := 'a'; c <= 'z'; c++ {
        l, r := strings.Index(s, string(c)), strings.LastIndex(s, string(c))
        mask := 0
        for i := l + 1; i < r; i++ {
            j := int(s[i] - 'a')
            if mask>>j&1 == 0 {
                mask |= 1 << j
                ans++
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function countPalindromicSubsequence(s: string): number {
    let ans = 0;
    const a = 'a'.charCodeAt(0);
    for (let ch = 0; ch < 26; ++ch) {
        const c = String.fromCharCode(ch + a);
        const l = s.indexOf(c);
        const r = s.lastIndexOf(c);
        let mask = 0;
        for (let i = l + 1; i < r; ++i) {
            const j = s.charCodeAt(i) - a;
            if (((mask >> j) & 1) ^ 1) {
                mask |= 1 << j;
                ++ans;
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
    pub fn count_palindromic_subsequence(s: String) -> i32 {
        let s_bytes = s.as_bytes();
        let mut ans = 0;
        for c in b'a'..=b'z' {
            if let (Some(l), Some(r)) = (
                s_bytes.iter().position(|&ch| ch == c),
                s_bytes.iter().rposition(|&ch| ch == c),
            ) {
                let mut mask = 0u32;
                for i in (l + 1)..r {
                    let j = (s_bytes[i] - b'a') as u32;
                    if (mask >> j & 1) == 0 {
                        mask |= 1 << j;
                        ans += 1;
                    }
                }
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @return {number}
 */
var countPalindromicSubsequence = function (s) {
    let ans = 0;
    const a = 'a'.charCodeAt(0);
    for (let ch = 0; ch < 26; ++ch) {
        const c = String.fromCharCode(ch + a);
        const l = s.indexOf(c);
        const r = s.lastIndexOf(c);
        let mask = 0;
        for (let i = l + 1; i < r; ++i) {
            const j = s.charCodeAt(i) - a;
            if (((mask >> j) & 1) ^ 1) {
                mask |= 1 << j;
                ++ans;
            }
        }
    }
    return ans;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class Solution {
    public int CountPalindromicSubsequence(string s) {
        int ans = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.IndexOf(c), r = s.LastIndexOf(c);
            int mask = 0;
            for (int i = l + 1; i < r; ++i) {
                int j = s[i] - 'a';
                if ((mask >> j & 1) == 0) {
                    mask |= 1 << j;
                    ++ans;
                }
            }
        }
        return ans;
    }
}

Comments