Palindromes And Indexes

Moderate
0/80
Average time to solve is 50m
profile
Contributed by
2 upvotes
Asked in companies
MicrosoftD.E.ShawNucleus Software

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
ababa
1 3
abaaa
2 2
Sample Output 1:
2
0
Explanation For Sample Output 1:
For the first test case aba, ababa are the two palindromic substrings.

For the second test case there are no palindromic substrings of length greater than 2 beginning with 2nd index.
Sample Input 2:
2
aaaaa
3 1
abc
3 3
Sample Output 2:
3
0
Hint

Try checking all possible substrings starting at index.

Approaches (2)
Brute Force

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’.
Time Complexity

O(N*N) where N is the length of the string in the input.


 We check for each substring beginning at index ‘i’ and spend O(N) time checking for palindrome. Hence total of O(N) * O(N) = O(N*N).

Space Complexity

O(N), where N is the length of the string in the input.

 

Since we only store the substring at any point of time and use constant space for checking for a palindrome. Hence the space complexity will be O(N). 

Code Solution
(100% EXP penalty)
Palindromes And Indexes
Full screen
Console