Count how many palindromic substring - from my coach

June 3, 2018

Introduction

It is my ninth mock interview with my coach. He gave me the dynamic programming solution to work on. It can be described "Given a string, you task is to count how many palindromic substring in this string."

I tried to get help from my coach, I like to see how he developed the solution using dynamic programming. Actually I found out that I missed the target.

Target

What is time complexity to solve the problem. The brute force solution will take time complexity O(n^3). The algorithm can be solved using dynamic programming with time complexity O(n^2).

All we have to do is to get dp[i, j] for any i, j from 0 to n where n is the length of string.

And then I can use O(n^2) to calculate the count of palindromic substring using O(n^2).