My friend had an online assessment with C3.ai recently. He said the questions are so hard and he could not pass all test cases and got a rejection mail the other day. I am also curious about how to solve the problem too so I am posting it here.

Given a string s, comprised of 0 and 1s, find the number of palindromic subsequences of length 5.
For instance, if s = 1011100,
then we count [0,2], [0,3] as different subsequences where each number is an index.
We tried to solve it with dfs + caching in python, but we were keep getting maximum recursion depth error. Any ideas on how to solve this problem?