Company: Walmart sparkplug
Difficulty: medium
SandwichString Given a string S. Your task is to determine the number of "sandwich substrings" found in S. A "sandwich substring" must meet the following criteria: The substring begins and ends with the same character. The structure of the middle part must satisfy: If the length of the substring is odd, the exact middle character is a vowel. If the length of the substring is even, the two middle characters are both vowels. All characters between the outermost characters and the middle character(s) (if any) must be consonants. The minimum length of a sandwich substring is 3. Note: The string consists only of lowercase letters from 'a' to 'z'. Input Format The first line of input contains an integer N representing the length of string. The second line contains string S of length N. Output Format Print a single integer representing the number of "sandwich substrings" found in the given string. Constraints 3≤ N ≤ 25 Sample Test Cases Sample Testcase 1: Input: 10 abcdcefgea Output: 1 Explan