Count Palindromic Subsequences of Length 3 - Jefeeerirs Online Assessment IIT Delhi

Problem Preview

"You are given a string **S** consisting of lowercase English letters. Count the total number of **palindromic subsequences** of length exactly **3**. A subsequence is obtained by deleting zero or more characters without changing the order of the remaining characters. A palindrome reads the same forwards and backwards. Print the total count. --- ### Input Format * First line contains the string **S**. --- ### Output Format Print a single integer representing the number of palindromic subsequences of length **3**. --- ### Constraints * (1 <= |S|<= 2 * 10^5) --- ### Example 1 #### Input ```text abca ``` #### Output ```text 2 ``` --- ### Explanation The valid palindromic subsequences are: * `aba` * `aca` --- ### Example 2 #### Input ```text aaa ``` #### Output ```text 1 ``` --- ### Example 3 #### Input ```text aaaa ``` #### Output ```text 4 ``` --- ### Explanation Choose any 3 of the 4 `'a'` characters: [ \binom{4}{3}=4 ] Hence the answer is **4**."