LeetCode Daily #3961: 29 Oct 2026 | Palindromic Path Queries in a Tree, XOR Masks and LCA

Brute to Best: the LeetCode problem of the day, from the naive solution to the optimal one. In this video: The problem: each edge of a tree carries a letter, and each query asks whether the letters along the path between two nodes can be rearranged into a palindrome The rearrangement rule: a multiset of letters forms a palindrome exactly when at most one letter has an odd count Brute force: walk the path for every query and tally the letters, which costs O(n) per query and times out when both n and the query count are large The key insight: only the parity of each letter matters, so a 26-bit mask with one bit per letter replaces the whole tally Root the tree and precompute mask[v], the XOR of all edge letters from the root down to v, in a single DFS For a query (u, v), the shared prefix above their lowest common ancestor appears in both masks and cancels, so pathMask = mask[u] XOR mask[v], and the LCA is not even needed in the final formula Answer true when popcount(pathMask) is at most 1 Finding the LCA with binary lifting when you want the path explicitly, in O(log n) per query Dry run: the path from node 3 to node 4 spells "bb", the mask is 0, and the answer is true Complexity: O(n) preprocessing and O(1) per query with the XOR trick, O(n + q) overall Problem: https://leetcode.com/problems/palindr... Related: Count Pairs Of Nodes (1782), Longest Path With Different Adjacent Characters (2246), Number of Wonderful Substrings (1915) Full Daily Challenge playlist on the channel. Subscribe for a new LeetCode daily problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode3961 #leetcodedaily #potd #palindromicpathqueries #tree #graph #bitmask #xor #lca #binarylifting #hard #coding #codinginterview #dsa #brutetobest