import java.util.ArrayList;

public class Solution {
    private char[] symbols;
    private int size;

    public String longestPalindrome(String s) {
        size = s.length();
        if (size < 2) {
            return s;
        }

        symbols = s.toCharArray();

        ArrayList<Pair> bases = new ArrayList<>(7);
        Pair pair = null;
        for (int i = 0; i < size - 1; i++) {
            if (pair == null && symbols[i] == symbols[i + 1]) {
                pair = new Pair(i, i + 1);
                continue;
            }
            if (pair != null && symbols[i] != symbols[i + 1]) {
                pair.right = i;
                bases.add(pair);
                pair = null;
            }
        }
        if (pair != null) {
            pair.right = size - 1;
            bases.add(pair);
        }

        for (int i = 0; i < size - 2; i++) {
            if (symbols[i] == symbols[i + 2]) {
                bases.add(new Pair(i, i + 2));
            }
        }

        if (bases.isEmpty()) {
            return s.substring(0, 1);
        }

        Pair longest = new Pair(0, -1);
        for (int i = 0; i < bases.size(); i++) {
            Pair expand = expand(bases.get(i));
            if (expand.right - expand.left > longest.right - longest.left) {
                longest = expand;
            }
        }

        return s.substring(longest.left, longest.right + 1);
    }

    private Pair expand(Pair initial) {
        Pair result = new Pair(initial.left, initial.right);
        while (result.left > 0 && result.right < size - 1) {
            int left = result.left - 1;
            int right = result.right + 1;
            if (symbols[left] != symbols[right]) {
                break;
            }
            result.left = left;
            result.right = right;
        }
        return result;
    }
}

class Pair {
    int left;
    int right;

    Pair(int left, int right) {
        this.left = left;
        this.right = right;
    }
}