Programming coding interview question.

Question: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Java solution.

public class MainClass {
    public static void main(String[] args) {
        String s = "tattarattat";        System.out.println(longestPalindrome(s));
    }

     static  String longestPalindrome(String s) {
         int start = 0;         int end = 0;         if(s.length() == 0){
             return "";         }else{
             for(int center = 0; center < s.length(); center++){
                 int len1 = PaliLength(center, center, s);                 int len2 = PaliLength(center, center + 1, s);                 if(len1 > end - start){
                     start = center - len1 / 2;                     end = center + len1 / 2;                 }
                 if(len2 > end - start){
                     start = center + 1 - len2/2;                     end = center + len2 / 2;                 }
             }
         }
         return s.substring(start, end + 1);    }

    public static int PaliLength(int L, int R, String s){
        int len = 0;        while(L >= 0 && R < s.length()){
            if(s.charAt(L) == s.charAt(R)){
                len = R - L + 1;                L--;                R++;            }else{
                break;            }
        }
        return len;    }
}

Comments

Popular posts from this blog

How to write to a file in Kotlin

Python Tkinter example