Question

Write an algorithm to find the substring from the given string that is the same when read forwards and backwards. Input The input consists of a stringinputStr, representing the given string for the puzzle. Output From the given string, print a substring which is the same when read forwards and backwards. Note If there are multiple sub-strings of equal length, choose the lexicographically smallest one. If there is no sub-string that is the Examples Example 1: Input: YABCCBAZ Output: ABCCBA Explanation: Given string is "YABCCBAZ", in this only sub-string which is same when read forward and backward is "ABCCBA".

Answer 1

To find the longest palindrome substring in a string, iterate over all possible substrings, check for palindromicity, and keep track of the longest one found, preferring lexicographically smaller ones in case of ties.

Step-by-step explanation:

To find a substring in a string that is the same when read forwards and backwards (a palindrome), one can use a nested loop algorithm. The key is to iterate over each possible starting and ending point in the string, and check if the substring defined by these points is a palindrome. If it is, and if its length is greater than the currently known longest palindrome, keep track of it. If multiple substrings of the same length are found, keep the lexicographically smallest one.

Algorithm :

1. Initialize the longest palindrome substring (longestPalindrome) as an empty string.
2. Iterate over the string with two nested loops. The outer loop (i) represents the starting point and the inner loop (j) represents the ending point of the substring.
3. For each substring (inputStr.substring(i, j)), check whether it is a palindrome and if it is longer than the current longestPalindrome. If both conditions are satisfied, update the longestPalindrome.
4. If two substrings of the same length are found, update the longestPalindrome only if the new substring is lexicographically smaller.
5. Continue until all possible substrings have been checked.
6. Print the longest palindrome substring found.
   

Here is the example given:

Input: "YABCCBAZ"

Output: "ABCCBA"

Explanation: The given string is "YABCCBAZ", and the longest palindrome substring is "ABCCBA", which is the same when read forwards and backwards.