Algorithm: Longest Continuous Palindrome in a String

Prerequisite: Basic programming experience in any language
Problem: Given a string find the longest continuous palindrome in it. We should not change position of any character, instead we should find how many palindromes are there and which is longest among them. For ex: if given input string is "madam" then possible palindromes are ("m", "a", "d", "a", "m", "ada", "madam") output would be "madam" as its longest palindrome. Or if given input is "Crore" output would be "ror"
If you still have confusion in understanding the problem, refer below link
https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/
For this problem we can assume given input contains all lower case character only.
I will write code in Java, But you can apply this logic to any language of your choice.
Approach 1- Brute Force:
 A brute force solution would be to consider/generate all substring and check if they are palindrome and find the largest among the string which are palindrome. This algorithm will run in O(n³) considering n is length of the string.
Approach 2:
 We can reduce the time complexity to O(n²) by following below method.
To solve this problem we can try to find largest palindrome from each index. For each index we will keep two pointer start and end. start index will represent left side and end index will be right side. We will check if character at both index is same then we will move start to further left and end to further right. We keep doing it until the character at left and right index are not same. Finally our substring would be palindrome. This result we will compare with the length of previous result and if its greater we will update the result. Below is the complete code for this

public static String longestPalindrome(String str) {
    if (str == null || str.length() <= 1) return str;
    String res = str.substring(0,1);
    for (int i = 0; i < str.length(); i++) {
        String str1 = expands(str, i, i);

        String str2 = expands(str, i, i + 1);
        if(str1.length()>res.length()){
            res = str1;
        }
        if(str2.length()>res.length()){
            res = str2;
        }

    }

    return res;
}


private static String expands(String str, int start, int end) {
    while(start>=0&& end<str.length() &&  str.charAt(start)==str.charAt(end)){
        start--;
        end++;
    }
    return  str.substring(start+1, end);
}

This algorithm run has time complexity of O(n²).
Approach 3:
 If you see previous problem we are creating many substring which is memory wastage.We can still improve our algorithm to avoid creating substring each time and instead return length from expand method. And based on length we can have our start and end index which can be used to extract final subString. Below is the code to do this.

public static String longestPalindromic(String str) {
    if (str == null || str.length() <= 1) return str;
    int start = 0;
    int end = 0;
    for (int i = 0; i < str.length(); i++) {
        int len1 = expand(str, i, i);
        int len2 = expand(str, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return str.substring(start, end + 1);
}


private static int expand(String str, int start, int end) {
    while (start >= 0 && end < str.length() && str.charAt(start) ==     str.charAt(end)) {
        start--;
        end++;
    }
    return end - start - 1;
}

Thank you for reading. Do comment if any bug found.
You can follow me on Twitter and GitHub