Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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.
"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 <= 105s consists of only lowercase English letters.Problem summary: 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".
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Bit Manipulation
"aabca"
"adc"
"bbcbaba"
count-palindromic-subsequences)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1930: Unique Length-3 Palindromic Subsequences
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;
}
}
// Accepted solution for LeetCode #1930: Unique Length-3 Palindromic Subsequences
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
}
# Accepted solution for LeetCode #1930: Unique Length-3 Palindromic Subsequences
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
// Accepted solution for LeetCode #1930: Unique Length-3 Palindromic Subsequences
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
}
}
// Accepted solution for LeetCode #1930: Unique Length-3 Palindromic Subsequences
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;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.