CompetitiveProgramming/LongestPalindromicSubstring.java at master · hdelcampo/CompetitiveProgramming · 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
class Solution {

    //Time: O(n^2), where n is s length
    //Space: O(1)
    public String longestPalindrome(String s) {

        String longestPal = "";

        for(int i = 0; i < s.length(); i++) {
            int offset1 = expandOffset(s, i, i);
            int offset2 = expandOffset(s, i, i + 1);

            String subs = "";

            int maxOffset = Math.max(offset1, offset2);

            if (offset2 > offset1) {
                subs = s.substring(i - maxOffset + 1, i + maxOffset + 1);
            } else {
                subs = s.substring(i - maxOffset, i + maxOffset + 1);
            }

            if (longestPal.length() < subs.length()) longestPal = subs;

        }

        return longestPal;

    }

    private int expandOffset(String s, int left, int right) {

        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }

        return (right - left - 1) / 2;

    }

}