Google OA 2024 - String of Lowercase English Alphabets

You are given a string of lowercase English alphabets. Your task is to find the number of palindromic triplets in the string. A palindromic triplet consists of three non-overlapping substrings S1, S2, and S3 such that each substring is a palindrome and all substrings are non-overlapping.

Test Case 1:

Input: `abaa`  

Expected Output: `5`  

Explanation: There are 5 different palindromic triplets in the string "abaa".

Expected Time Complexity: O(n^2)