System Engineer

You have been given a 2-D matrix ‘MAT’ of size ‘N’ x ‘N’ i.e. N rows and N columns. Your task is to find the maximum value of ‘MAT[a][b]’ - ‘MAT[c][d]’ over all possible indices (0 <= ‘a’, ‘b’, ‘c’, ‘d’ < ‘N’) such that . ‘a’ > ‘c’ and ‘b’ > ‘d’.

For example:

In this example, to maximise the value of ‘MAT[a][b]’ - ‘MAT[c][d]’ fulfilling the given conditions on indices (‘a’ > ‘c’ and ‘b’ > ‘d’), we take ‘a’ = 2, ‘b’ = 2, ‘c’ = 0 and ‘d’ = 0 .  So, ‘MAT[a][b]’ = 9 and ‘MAT[c][d]’ = 1 and the value of ‘MAT[a][b]’ - ‘MAT[c][d]’ => 9 - 1 = 8 which is maximum among all possible combinations.

You are given a number 'N' in the form of a string 'S', which is a palindrome. You need to find the greatest number strictly less than 'N' which is also a palindrome.

Note:

1. A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as madam, racecar, 1234321, etc.
2. The numerical value of the given string S will be greater than 0.
3. A single-digit number is also considered a palindrome.
4. The answer number should not contain any leading zeros, except for the case when the answer is 0.
5. Note that the length of the string is nothing but the number of digits in N.