SDE - Intern

You are given a string 'str' of length 'N'.

Your task is to return the longest palindromic substring. If there are multiple strings, return any.

A substring is a contiguous segment of a string.

For example :

str = "ababc"

The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome. 

There is another palindromic substring of length 3 is "bab". Since starting index of "aba" is less than "bab", so "aba" is the answer.

Sushant is learning about palindromes. One day his teacher gave him a string ‘STR’ consisting of only the lowercase letters and asked him to modify the string in such a way that the string doesn’t contain any palindromic substring by replacing the minimum characters present in the given string. Sushant, although a brilliant student, needs your help.

Note:

A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as “madam” or “racecar”.

Example:

Given an ‘STR’: ‘aaaaaaa’ The minimum characters that will be replaced are 4. The string can be converted into ‘abcabca’.

Note:

Here are multiple possible answers, for example changing all the elements, but we have to find the minimum replacements possible.