class Solution {

    class Node {
        char val;
        int idx;
        Node (char val, int idx) {
            this.val = val;
            this.idx = idx;
        }
        public String toString() {
            return "[" + val + ", " + idx + "]";
        }
    }

    public String longestPalindrome(String s) {
        int len = s.length();
        char[] sChar = s.toCharArray();
        if(len < 3) {
            if(len == 1 || sChar[0] == sChar[1]) return s;
            else return s.substring(0, 1);
        }
        if (allSame(sChar)) return s;
        ArrayDeque<Node> stack = new ArrayDeque<>();
        
        String res = "";
        stack.push(new Node(sChar[0], 0));
        for (int i = 1; i < len; i++) {
            char c = sChar[i];
            if (stack.peek().val == c) {
                res = getLongestPallindrome(new ArrayDeque<>(stack), res, i, sChar, s);
                Node temp = stack.pop();
                if (!stack.isEmpty() && stack.peek().val == c) {
                    res = getLongestPallindrome(new ArrayDeque<>(stack), res, i, sChar, s);
                }
                stack.push(temp);
            } else {
                Node temp = stack.pop();
                if (!stack.isEmpty() && stack.peek().val == c) {
                    res = getLongestPallindrome(new ArrayDeque<>(stack), res, i, sChar, s);
                }
                stack.push(temp);
            }
            stack.push(new Node(c, i));
        }
        return res.equals("") ? s.substring(0, 1) : res;
    }

    private String getLongestPallindrome(ArrayDeque<Node> stack, String res, int idx, char[] sChar, String s) {
        int startIdx = 0;
        while(idx < sChar.length && !stack.isEmpty() && stack.peek().val == sChar[idx]) {
            startIdx = stack.pop().idx;
            idx++;
        }
        return (idx - startIdx > res.length()) ? s.substring(startIdx, idx) : res;
    }

    private boolean allSame(char[] sChar) {
        for(int i = 1; i < sChar.length; i++) {
            if (sChar[i] != sChar[i - 1]) return false;
        }
        return true;
    }
}