Palindromes And Indexes
Last Updated: 7 Jul, 2021
Difficulty: Moderate
You are given a string S consisting of lowercase characters only, an index ‘i’ and length ‘len’. Your task is to find the count of all palindromic substrings in the string ‘S’ which start at index ‘i’ and have a length of at least ‘len’.
A string is called palindromic if it reads the same backward as forward. ex "aba" is a palindrome but "abaab" is not a palindrome.
Note: A substring is a contiguous non-empty segment of the string.
For example:
String S = ababa
Index i = 1
len = 3
The answer to the above test case is 2 since there are two substrings that start at index 1 (1 - based indexing) - “aba”, “ababa”. Both these have a length of at least 3.
Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains the string S.
The next line contains 2 space-separated integers denoting index ‘i’ and length ‘len’.
Output Format:
For each test case, print an integer denoting the number of possible strings.
Output for each test case will be printed in a separate line.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= |S| <= 10^4
1 <= i, len <= N
Time Limit: 1 sec.
Approach 1
We can check for all possible substrings starting at index ‘i’ and if they have lengths greater than ‘LEN’ and are palindrome we can increment the answer.
Algorithm:
palindromesAtIndex(‘S’, i, ‘LEN’) takes string, index, and length as input and returns the number of palindromic substrings starting at index ‘i’ with length at least ‘LEN’.
- Initialize a variable ‘ANS’ of type int to store the count of possible substrings.
- Start at index ‘i’ and keep the other pointer at index ‘i’ + ‘LEN’ - ‘1’.
- Check if the substring [i, j] is a palindrome or not. If yes, increment the ‘ANS’.
- Increment the other end of the substring.
- Return ‘ANS’.
Approach 2
We will use the idea of manacher’s Algorithm to compute the length of the largest palindrome starting at each index. We transform the string by adding ‘#’ between every character so that every palindrome is now of odd length and the original length can be found out by taking the floor(L/2) of the new length.
For every index, in the string, we check for the palindrome centered at this index and check if it covers our index ‘i’ and has a length of at least ‘LEN’. If yes we increment the answer by 1.
Algorithm:
palindromesAtIndex(‘S’, ‘i’, ‘LEN’) takes a string, index, and length as input and returns the number of palindromic substrings starting at index ‘i’ with length at least ‘LEN’.
- We first transform the string using the transform function.
- We then calculate the manacher’s array P for this new string.
- Start at index i and keep the other pointer j at index i + ‘LEN’ - 1.
- Check if the value of P[j] is greater than or equal to ‘LEN and covers the index i.
- If yes, increment the answer.
- Increment the pointer to the next index
- Return the final answer.
transform(S) takes a string S as input and returns the string with ‘#’ after every character and before the first character.
- manacher(S) takes a string S as input and returns the manacher’s array of the string S where each index of the array stores the length of the longest palindrome centered at i.
