Posts Longest Palindrome in a String (geeksforgeeks - SDE Sheet)
Post
Cancel

Longest Palindrome in a String (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given a string str, find the longest palindromic substring in str. Substring of string str: str[ i . . . . j ] where 0 ≤ i ≤ j < len(str). Return the longest palindromic substring of str.

Palindrome string: A string that reads the same backward. More formally, str is a palindrome if reverse(str) = str. In case of conflict, return the substring which occurs first ( with the least starting index).

geeksforgeeks

SOLUTION

At each position, assume it’s the mid and try to form the largest palindrome using two pointers left and right. We may have odd or even length palindromes and they can be handled separately.

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
54
55
56
57
58
59
60
61
62
class Solution{

    static String longestPalin(String s){

        int n = s.length();
        int maxLength = 1;

        int l = 0;
        int r = 0;

        int resL = 0;
        int resR = 0;

        for(int i=0; i<n; i++){

            // odd
            l = i;
            r = i;

            while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
                l--;
                r++;
            }

            if(r-l-1 > maxLength){

                resL = l + 1;
                resR = r - 1;

                maxLength = Math.max(maxLength, resR - resL + 1);
            }


            // even
            if(i < n-1 && s.charAt(i) == s.charAt(i+1)){

                l = i;
                r = i+1;

                while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
                    l--;
                    r++;
                }

                if(r-l-1 > maxLength){

                    resL = l + 1;
                    resR = r - 1;

                    maxLength = Math.max(maxLength, resR - resL + 1);
                }


            }

        }

        return s.substring(resL, resR + 1);

    }

}
This post is licensed under CC BY 4.0 by the author.