Leetcode-problems/problem5.java at main · tejatayi/Leetcode-problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//5. Longest Palindromic Substring

public class problem5 {

    public static int checkPalin(char[] a , int l ,int r, int len)
    {
        while(l>=0 && r<len)
        {
            if(a[l]!=a[r])
            break;

            l--;r++;
        }

        return (r-l)-1;
    }

    public static String longestPalindrome(String s) {
        char [] a = s.toCharArray();
        int len = s.length();

        int start =0,end=0;

        for(int i =0 ;i<len;i++)
        {
            int l=i,r=i;

            int l1 = checkPalin(a, l, r, len);
            int l2 = checkPalin(a, l, r+1, len);
            int maxlen = Math.max(l1, l2);

            if (maxlen > end - start) {
                // Update start and end based on new palindrome bounds
                start = i - (maxlen - 1) / 2;
                end = i + maxlen / 2;
            }

        }

        return s.substring(start, end+1);

    }


    public static void main(String[] args) {
        String a = "babad";

        System.out.println(longestPalindrome(a));


    }
}