You are given an undirected tree with n nodes labeled 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between nodes ui and vi.
You are also given a string s of length n consisting of lowercase English letters, where s[i] represents the character assigned to node i.
You are also given a string array queries, where each queries[i] is either:
"update ui c": Change the character at node ui to c. Formally, update s[ui] = c."query ui vi": Determine whether the string formed by the characters on the unique path from ui to vi (inclusive) can be rearranged into a palindrome.Return a boolean array answer, where answer[j] is true if the jth query of type "query ui vi" can be rearranged into a palindrome, and false otherwise.
Example 1:
Input: n = 3, edges = [[0,1],[1,2]], s = "aac", queries = ["query 0 2","update 1 b","query 0 2"]
Output: [true,false]
Explanation:
"query 0 2": Path 0 → 1 → 2 gives "aac", which can be rearranged to form "aca", a palindrome. Thus, answer[0] = true."update 1 b": Update node 1 to 'b', now s = "abc"."query 0 2": Path characters are "abc", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.Thus, answer = [true, false].
Example 2:
Input: n = 4, edges = [[0,1],[0,2],[0,3]], s = "abca", queries = ["query 1 2","update 0 b","query 2 3","update 3 a","query 1 3"]
Output: [false,false,true]
Explanation:
"query 1 2": Path 1 → 0 → 2 gives "bac", which cannot be rearranged to form a palindrome. Thus, answer[0] = false."update 0 b": Update node 0 to 'b', now s = "bbca"."query 2 3": Path 2 → 0 → 3 gives "cba", which cannot be rearranged to form a palindrome. Thus, answer[1] = false."update 3 a": Update node 3 to 'a', s = "bbca"."query 1 3": Path 1 → 0 → 3 gives "bba", which can be rearranged to form "bab", a palindrome. Thus, answer[2] = true.Thus, answer = [false, false, true].
Constraints:
1 <= n == s.length <= 5 * 104edges.length == n - 1edges[i] = [ui, vi]0 <= ui, vi <= n - 1s consists of lowercase English letters.edges represents a valid tree.1 <= queries.length <= 5 * 104
queries[i] = "update ui c" orqueries[i] = "query ui vi"0 <= ui, vi <= n - 1c is a lowercase English letter.Solutions for this problem are being prepared.
Try solving it yourselfPractice Palindromic Path Queries in a Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor