Palindrome Substrings

Given a string STR, your objective is to determine the total count of palindromic substrings within it.

Input:

The first line contains an integer 't', the number of test cases. Each subsequent line consists of a string 'STR'.

Output:

For each test case, output the total number of palindromic substrings of the given string on a new line.

Example:

If the input is:

abbc

The output should be:

5

Explanation: The palindromic substrings are ['a', 'b', 'b', 'c', 'bb'].

Constraints:

1

Question

Given a string STR, your objective is to determine the total count of palindromic substrings within it.

The first line contains an integer 't', the number of test cases. Each subsequent line consists of a string 'STR'.

For each test case, output the total number of palindromic substrings of the given string on a new line.

If the input is:

abbc

The output should be:

Explanation: The palindromic substrings are ['a', 'b', 'b', 'c', 'bb'].

A string is considered a palindrome if it reads the same forwards and backwards.

Accepted Answer

Count the total number of palindromic substrings in a given string.

Iterate through each character in the string and expand around it to find palindromic substrings.
Use dynamic programming to optimize the solution by storing previously computed results.
Consider both odd and even length palindromes while counting.
Example: For input 'abbc', the output should be 5 (['a', 'b', 'b', 'c', 'bb']).

Sourcefuse Technologies Software Developer Intern interview questions & answers