class Solution {
    public int longestPalindrome(String s) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                set.remove(c);
            } else {
                set.add(c);
            }
        }
        int odd = set.size();
        return s.length() - (odd == 0 ? 0 : odd - 1);
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] one = new int[26];
        for (int i = 0; i < ransomNote.length(); i++) {
            int idx = ransomNote.charAt(i) - 'a';
            one[idx] += 1;
        }
        for (int i = 0; i < magazine.length(); i++) {
            int idx = magazine.charAt(i) - 'a';
            if (one[idx] != 0) {
                one[idx] -= 1;
            }
        }
        for (int num : one) {
            if (num > 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> charNum = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            charNum.put(currentChar, charNum.getOrDefault(currentChar, 0) + 1);
        }

        for (int i = 0; i < t.length(); i++) {
            char currentChar = t.charAt(i);
            if (charNum.containsKey(currentChar)) {
                charNum.put(currentChar, charNum.get(currentChar) - 1);
                if (charNum.get(currentChar) == 0) {
                    charNum.remove(currentChar);
                }
            } else {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode currentNode = root;
        while (true) {
            if (p.val < currentNode.val && q.val < currentNode.val) {
                currentNode = currentNode.left;
            } else if (p.val > currentNode.val && q.val > currentNode.val) {
                currentNode = currentNode.right;
            } else {
                return currentNode;
            }
        }
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return root;
        if (root.left != null)
            invertTree(root.left);
        if (root.right != null)
            invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> visited = new HashSet<>();
        for (int num : nums) {
            if (!visited.add(num)) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;
        ListNode first = head;
        ListNode second = head.next;
        while (second != null && second.next != null) {
            first = first.next;
            second = second.next.next;
            if (first == second)
                return true;
        }
        return false;
    }
}

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        char[] c = s.toCharArray();

        int left = 0;
        int right = c.length - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(c[left])) {
                left += 1;
            }
            while (left < right && !Character.isLetterOrDigit(c[right])) {
                right -= 1;
            }
            if (left != right && c[left] != c[right]) {
                return false;
            } else if (left == right) {
                break;
            } else {
                left += 1;
                right -= 1;
            }
        }
        return true;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        int buyinPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            buyinPrice = Math.min(buyinPrice, prices[i]);
            profit = Math.max(profit, prices[i] - buyinPrice);
        }
        return profit;
    }
}