FastPrepFastPrep
Problem Brief

Graph Palindrome Queries

FULLTIMEOA

You are given an undirected graph rooted at node 0 with n nodes (numbered 0 to n-1). Each node i is labelled with a lowercase English letter given by labels[i].

You are also given m queries. For each query [node_from, node_to], collect all characters encountered while travelling from node_from to node_to along the unique path in the tree. Determine whether those characters can be rearranged to form a palindrome.

Return a boolean array of length m where result[i] is true if the characters for query i can form a palindrome, and false otherwise.

1Example 1

Input
n = 3, labels = "aba", edges = [[0, 1], [1, 2]], queries = [[0, 2], [0, 1]]
Output
[true, false]
Explanation

Query [0,2]: path is 0→1→2, chars = {a, b, a} → {a:2, b:1} → one odd-count char → can form palindrome → true.
Query [0,1]: path is 0→1, chars = {a, b} → {a:1, b:1} → two odd-count chars → cannot form palindrome → false.

2Example 2

Input
n = 2, labels = "aa", edges = [[0, 1]], queries = [[0, 1]]
Output
[true]
Explanation

Path 0→1 yields {a, a} → {a:2} → zero odd-count chars → true.

3Example 3

Input
n = 4, labels = "abcd", edges = [[0, 1], [0, 2], [0, 3]], queries = [[1, 2]]
Output
[false]
Explanation

Path 1→2 goes through node 0: chars = {b, a, c} → {a:1, b:1, c:1} → three odd-count chars → cannot form palindrome → false.

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 105
  • 1 ≤ m ≤ 105
  • labels contains only lowercase English letters
  • Edges form a valid tree rooted at node 0
public boolean[] palindromeQueries(int n, String labels, int[][] edges, int[][] queries) {
    // write your code here
}
Input

n

3

labels

"aba"

edges

[[0, 1], [1, 2]]

queries

[[0, 2], [0, 1]]

Output

[true, false]

Sign in to submit your solution.