Count unique characters between each pair of the same chars
Approach
building a HashSet can be slower then just checking for contains 26 times
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(1)$$
Code
fun countPalindromicSubsequence(s: String) =
('a'..'z').sumOf { c ->
val s = s.slice(s.indexOf(c) + 1..< s.lastIndexOf(c))
('a'..'z').count { it in s }
}
pub fn count_palindromic_subsequence(s: String) -> i32 {
('a'..='z').map(|c| {
let i = s.find(c).unwrap_or(0);
let j = s.rfind(c).unwrap_or(0);
if i + 1 >= j { 0 } else
{ ('a'..='z').filter(|&c| s[i+1..j].contains(c)).count() }
}).sum::<usize>() as i32
}
int countPalindromicSubsequence(string s) {
int f[26] = {}, l[26] = {}, r = 0; fill(f, f+26, INT_MAX);
for (int i = 0; i < s.size(); ++i)
f[s[i] - 'a'] = min(f[s[i] - 'a'], i), l[s[i] - 'a'] = i;
for (int i = 0; i < 26; ++i) if (f[i] < l[i])
r += unordered_set<char>(begin(s) + f[i] + 1, begin(s) + l[i]).size();
return r;
}
Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.
