Sourav and Subsequences (Easy Version)

0

0 votes
Problem

Given a string S of size N, made up of only 3 characters a, b, c . Find the number of subsequences of String S of length 3 which are palindrome.  A palindrome is a string that reads the same backward as forward. 

 

Input Format

Given T test case,

Each test case consists of 2 lines 

Line 1 contains a number N denoting the size of the string

Line 2 contains the String S

Output Format

Print a single integer for each test case which is the number of subsequences of string S of length 3 which are palindrome.

Constraints

  • 1<=T<=10
  • 1<=N<=100.
Sample Input
2
5
abbca
6
abcabc
Sample Output
3
6
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

In first test case 

String S = abbca , palindromic subsequences are [ { 0,1,4 } , {0,2,4} , {0,3,4} ] , so answer = 3

Note:- here 0,1,2,3,4 are indexes of characters taken in the subsequence   

In second test case

String S = abcabc, palindromic subsequences are [ {0,1,3} , {0,2,3} , {1,2,4} , {1,3,4} , {2,3,5} , {2,4,5} ] , so answer = 6

Editor Image

?