The professor is planning a heist, this time in England. He along with his team of robbers want to break into the Jewel House at the Tower of London to steal the Kohinoor.
He has done his research and found that the lock of the Jewel House is password encrypted. The password is of length len and it is in lowercase ['a'-'z']. From his research, the professor got to know that password have, p number of pairs (L, R) which signifies the starting and ending position of the substring and every such substring must be a palindrome.
Given the values, calculate how many times the robbers have to input the password to try all possible passwords.
As the answer can be large, print it modulus 1000000007 (1e9+7).
Example:
Input
len = 4
p=3
pairs are [[1.2]
12,3],
[3.4]
Output
26
Not sure If I'm correct but first remove every pair which is not in the string; and if there is a pair such as [len — x, len + y] x,y >= 0 simplify it to the parts that matter(e.g: len= 10, pair: [8,11], new = [9,10]), and sort the pairs; then use combinatorics to determine the first half of the first pair, after that ignore the intersections and redo the task for new ones what do I mean by ignoring intersections: [4, 6],[5,7]. since index 5,6 are already counted in the first pair, to stay palindrome s[7] should be s[5]
One approach (dependent on constraints) might be to check which indices have to be equal to each other for the palindromes to hold. For example, if you were given a pair (1, 3) you would know that the first character must be equal to the third, otherwise that substring wouldn't be palindromic.
So, starting from the first character, check which characters must be equal to this by going over every pair and seeing if that character lies within it (this part can be optimized w/ sortings). Then, check all the characters you've just shown to be equal to the first to see what characters must be equal to them, and etc etc until you find all of them. Then check 2nd character (or first non searched char) and do the same, and so on until you find the total number of groups of characters that must be the same. The answer would then be 26 to the power of the number of groups, as each group can be given one character.
Without optimizations, this runs in O(len * no# pairs) (i think) (might be wrong) (idk)