Given a string S(consisting of only lower case characters) and Q queries.

Given a string S(consisting of only lower case characters) and Q queries.

Software Engineering practical Coding Questions

In each query you will given an integer i and your task is to find the length of longest odd palindromic substring whose middle index is i.

Note:

1.) Assume 1 based indexing.

2.) Longest odd palindrome: A palindrome substring whose length is odd.

Problem Constraints

1<=|s|,Q<=1e5

1<=i<=|s|

 

Input Format

First argument A is string S.

Second argument B is an array of integers where B[i] denotes the query index of ith query.

Ouput Format

Return an array of integers where ith integer denotes the answer of ith query.

Example Input

Input 1:

A=aaaaa

B=[2,3]

Input 2:

A=abcd

B=[2]

Example Output

Ouput 1:

[3,5]

Ouput 1:

[0]

Example Explanation

Explanation 1:

 For first query longest palindrome is aaa.

For second query whole string is the longest palindrome.

Explanation 1:

 No palindrome present.

Sol :- 

To solve this problem, we can use dynamic programming to pre-compute the lengths of the longest odd palindromic substrings for each possible middle index. Then, we can simply look up the answers for the given queries.

Here is some sample code in Python that demonstrates this approach:

Python

def longest_odd_palindromes(S, queries): # Initialize the DP array with all zeros dp = [0] * len(S) # Iterate through the characters of S for i in range(len(S)): # Initialize the length of the palindrome centered at i to 1 dp[i] = 1 # Expand the palindrome around i as far as possible l = i - 1 r = i + 1 while l >= 0 and r < len(S) and S[l] == S[r]: dp[i] += 2 l -= 1 r += 1 # Initialize the result array result = [] # Look up the answers for the given queries for i in queries: result.append(dp[i-1]) # Return the result array return result # Test the function print(longest_odd_palindromes("aaaaa", [2, 3])) # Expected output: [3, 5] print(longest_odd_palindromes("abcd", [2])) # Expected output: [0] This function takes in two arguments: S, which is the string, and queries, which is the array of queries. It returns an array containing the answers to the queries.

This function takes in two arguments: S, which is the string, and queries, which is the array of queries. It returns an array containing the answers to the queries.

To compute the lengths of the longest odd palindromic substrings, we use a dynamic programming approach. We initialize the DP array with all zeros, and then iterate through the characters of S. For each character, we initialize the length of the palindrome centered at that character to 1, and then expand the palind