Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: General problem-solving
3 [[0,1],[1,2]] "aac" ["query 0 2","update 1 b","query 0 2"]
4 [[0,1],[0,2],[0,3]] "abca" ["query 1 2","update 0 b","query 2 3","update 3 a","query 1 3"]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3841: Palindromic Path Queries in a Tree
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3841: Palindromic Path Queries in a Tree
// package main
//
// import (
// "math/bits"
// "strconv"
// "strings"
// )
//
// // https://space.bilibili.com/206214
// // 模板来自我的题单 https://leetcode.cn/circle/discuss/mOr1u6/
// type fenwick []int
//
// func newFenwickTree(n int) fenwick {
// return make(fenwick, n+1) // 使用下标 1 到 n
// }
//
// // a[i] ^= val
// // 1 <= i <= n
// // 时间复杂度 O(log n)
// func (f fenwick) update(i int, val int) {
// for ; i < len(f); i += i & -i {
// f[i] ^= val
// }
// }
//
// // 计算前缀异或和 a[1] ^ ... ^ a[i]
// // 1 <= i <= n
// // 时间复杂度 O(log n)
// func (f fenwick) pre(i int) (res int) {
// for ; i > 0; i &= i - 1 {
// res ^= f[i]
// }
// return
// }
//
// func palindromePath(n int, edges [][]int, s string, queries []string) (ans []bool) {
// g := make([][]int, n)
// for _, e := range edges {
// x, y := e[0], e[1]
// g[x] = append(g[x], y)
// g[y] = append(g[y], x)
// }
//
// mx := bits.Len(uint(n))
// pa := make([][16]int, n)
// dep := make([]int, n)
// timeIn := make([]int, n) // DFS 时间戳
// timeOut := make([]int, n)
// clock := 0
// pathXorFromRoot := make([]int, n) // 从根开始的路径中的字母奇偶性的集合
// pathXorFromRoot[0] = 1 << (s[0] - 'a')
//
// var dfs func(int, int)
// dfs = func(x, p int) {
// pa[x][0] = p
// clock++
// timeIn[x] = clock
// for _, y := range g[x] {
// if y != p {
// dep[y] = dep[x] + 1
// pathXorFromRoot[y] = pathXorFromRoot[x] ^ 1<<(s[y]-'a')
// dfs(y, x)
// }
// }
// timeOut[x] = clock
// }
// dfs(0, -1)
//
// for i := range mx - 1 {
// for x := range pa {
// p := pa[x][i]
// if p != -1 {
// pa[x][i+1] = pa[p][i]
// } else {
// pa[x][i+1] = -1
// }
// }
// }
//
// uptoDep := func(x, d int) int {
// for k := uint32(dep[x] - d); k > 0; k &= k - 1 {
// x = pa[x][bits.TrailingZeros32(k)]
// }
// return x
// }
//
// // 返回 x 和 y 的最近公共祖先
// getLCA := func(x, y int) int {
// if dep[x] > dep[y] {
// x, y = y, x
// }
// y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
// if y == x {
// return x
// }
// for i := mx - 1; i >= 0; i-- {
// px, py := pa[x][i], pa[y][i]
// if px != py {
// x, y = px, py // 同时往上跳 2^i 步
// }
// }
// return pa[x][0]
// }
//
// // 上面全是模板，下面开始本题逻辑
//
// t := []byte(s)
// f := newFenwickTree(n) // 注意树状数组是异或运算
// for _, q := range queries {
// if q[0] == 'u' {
// x, _ := strconv.Atoi(q[7 : len(q)-2])
// c := q[len(q)-1]
// val := 1<<(t[x]-'a') ^ 1<<(c-'a') // 擦除旧的，换上新的
// t[x] = c
// // 子树 x 全部异或 val，转换成对区间 [timeIn[x], timeOut[x]] 的差分更新
// f.update(timeIn[x], val)
// f.update(timeOut[x]+1, val)
// } else {
// q = q[6:]
// i := strings.IndexByte(q, ' ')
// x, _ := strconv.Atoi(q[:i])
// y, _ := strconv.Atoi(q[i+1:])
// lca := getLCA(x, y)
// res := pathXorFromRoot[x] ^ pathXorFromRoot[y] ^ f.pre(timeIn[x]) ^ f.pre(timeIn[y]) ^ 1<<(t[lca]-'a')
// ans = append(ans, res&(res-1) == 0) // 至多一个字母的出现次数是奇数
// }
// }
// return
// }
// Accepted solution for LeetCode #3841: Palindromic Path Queries in a Tree
package main
import (
"math/bits"
"strconv"
"strings"
)
// https://space.bilibili.com/206214
// 模板来自我的题单 https://leetcode.cn/circle/discuss/mOr1u6/
type fenwick []int
func newFenwickTree(n int) fenwick {
return make(fenwick, n+1) // 使用下标 1 到 n
}
// a[i] ^= val
// 1 <= i <= n
// 时间复杂度 O(log n)
func (f fenwick) update(i int, val int) {
for ; i < len(f); i += i & -i {
f[i] ^= val
}
}
// 计算前缀异或和 a[1] ^ ... ^ a[i]
// 1 <= i <= n
// 时间复杂度 O(log n)
func (f fenwick) pre(i int) (res int) {
for ; i > 0; i &= i - 1 {
res ^= f[i]
}
return
}
func palindromePath(n int, edges [][]int, s string, queries []string) (ans []bool) {
g := make([][]int, n)
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
mx := bits.Len(uint(n))
pa := make([][16]int, n)
dep := make([]int, n)
timeIn := make([]int, n) // DFS 时间戳
timeOut := make([]int, n)
clock := 0
pathXorFromRoot := make([]int, n) // 从根开始的路径中的字母奇偶性的集合
pathXorFromRoot[0] = 1 << (s[0] - 'a')
var dfs func(int, int)
dfs = func(x, p int) {
pa[x][0] = p
clock++
timeIn[x] = clock
for _, y := range g[x] {
if y != p {
dep[y] = dep[x] + 1
pathXorFromRoot[y] = pathXorFromRoot[x] ^ 1<<(s[y]-'a')
dfs(y, x)
}
}
timeOut[x] = clock
}
dfs(0, -1)
for i := range mx - 1 {
for x := range pa {
p := pa[x][i]
if p != -1 {
pa[x][i+1] = pa[p][i]
} else {
pa[x][i+1] = -1
}
}
}
uptoDep := func(x, d int) int {
for k := uint32(dep[x] - d); k > 0; k &= k - 1 {
x = pa[x][bits.TrailingZeros32(k)]
}
return x
}
// 返回 x 和 y 的最近公共祖先
getLCA := func(x, y int) int {
if dep[x] > dep[y] {
x, y = y, x
}
y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
if y == x {
return x
}
for i := mx - 1; i >= 0; i-- {
px, py := pa[x][i], pa[y][i]
if px != py {
x, y = px, py // 同时往上跳 2^i 步
}
}
return pa[x][0]
}
// 上面全是模板，下面开始本题逻辑
t := []byte(s)
f := newFenwickTree(n) // 注意树状数组是异或运算
for _, q := range queries {
if q[0] == 'u' {
x, _ := strconv.Atoi(q[7 : len(q)-2])
c := q[len(q)-1]
val := 1<<(t[x]-'a') ^ 1<<(c-'a') // 擦除旧的，换上新的
t[x] = c
// 子树 x 全部异或 val，转换成对区间 [timeIn[x], timeOut[x]] 的差分更新
f.update(timeIn[x], val)
f.update(timeOut[x]+1, val)
} else {
q = q[6:]
i := strings.IndexByte(q, ' ')
x, _ := strconv.Atoi(q[:i])
y, _ := strconv.Atoi(q[i+1:])
lca := getLCA(x, y)
res := pathXorFromRoot[x] ^ pathXorFromRoot[y] ^ f.pre(timeIn[x]) ^ f.pre(timeIn[y]) ^ 1<<(t[lca]-'a')
ans = append(ans, res&(res-1) == 0) // 至多一个字母的出现次数是奇数
}
}
return
}
# Accepted solution for LeetCode #3841: Palindromic Path Queries in a Tree
# Time: O((n + q) * logn)
# Space: O(n)
# hld, lca, fenwick tree
class Solution(object):
def palindromePath(self, n, edges, s, queries):
"""
:type n: int
:type edges: List[List[int]]
:type s: str
:type queries: List[str]
:rtype: List[bool]
"""
class BIT(object): # 0-indexed.
def __init__(self, n):
self.__bit = [0]*(n+1) # Extra one for dummy node.
def add(self, i, val):
i += 1 # Extra one for dummy node.
while i < len(self.__bit):
self.__bit[i] ^= val # modified
i += (i & -i)
def query(self, i):
i += 1 # Extra one for dummy node.
ret = 0
while i > 0:
ret ^= self.__bit[i] # modified
i -= (i & -i)
return ret
def build_hld(adj, cb):
parent, depth, size, heavy, head = [-1]*len(adj), [0]*len(adj), [1]*len(adj), [-1]*len(adj), list(range(len(adj)))
stk = [(1, 0, -1)]
while stk:
step, u, p = stk.pop()
if step == 1:
cb(u, p)
parent[u], depth[u] = p, (depth[p]+1 if p != -1 else 0)
stk.append((2, u, p))
for v in adj[u]:
if v == p:
continue
stk.append((1, v, u))
elif step == 2:
for v in adj[u]:
if v == parent[u]:
continue
size[u] += size[v]
if heavy[u] == -1 or size[v] > size[heavy[u]]:
heavy[u] = v
idx = -1
left, right = [-1]*len(adj), [-1]*len(adj)
stk = [(1, 0, 0)]
while stk:
step, u, h = stk.pop()
if step == 1:
idx += 1
head[u], left[u] = h, idx
stk.append((2, u, h))
for v in adj[u]:
if v == parent[u] or v == heavy[u]:
continue
stk.append((1, v, v))
if heavy[u] != -1:
stk.append((1, heavy[u], h))
elif step == 2:
right[u] = idx
return parent, depth, head, left, right
def lca(u, v):
while head[u] != head[v]:
if depth[head[u]] < depth[head[v]]:
u, v = v, u
u = parent[head[u]]
return u if depth[u] < depth[v] else v
def callback(u, p):
prefix[u] = (prefix[p] if p != -1 else 0)^(1<<(ord(s[u])-ord('a')))
s = list(s)
adj = [[] for _ in xrange(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
prefix = [0]*n
parent, depth, head, left, right = build_hld(adj, callback)
bit = BIT(n+1)
result = []
for q in queries:
args = q.split()
op = args[0]
u = int(args[1])
if op == "update":
c = args[2]
diff = (1<<(ord(s[u])-ord('a')))^(1<<(ord(c)-ord('a')))
if not diff:
continue
s[u] = c
bit.add(left[u], diff)
bit.add(right[u]+1, diff)
else:
v = int(args[2])
l = lca(u, v)
mask = (prefix[u]^bit.query(left[u]))^(prefix[v]^bit.query(left[v]))^(1<<(ord(s[l])-ord('a')))
result.append((mask&(mask-1)) == 0)
return result
# Time: O((n + q) * logn)
# Space: O(nlogn)
# dfs, lca, binary lifting, fenwick tree
class Solution2(object):
def palindromePath(self, n, edges, s, queries):
"""
:type n: int
:type edges: List[List[int]]
:type s: str
:type queries: List[str]
:rtype: List[bool]
"""
class BIT(object): # 0-indexed.
def __init__(self, n):
self.__bit = [0]*(n+1) # Extra one for dummy node.
def add(self, i, val):
i += 1 # Extra one for dummy node.
while i < len(self.__bit):
self.__bit[i] ^= val # modified
i += (i & -i)
def query(self, i):
i += 1 # Extra one for dummy node.
ret = 0
while i > 0:
ret ^= self.__bit[i] # modified
i -= (i & -i)
return ret
class TreeInfos(object): # Time: O(NlogN), Space: O(NlogN), N is the number of nodes
def __init__(self, adj):
N = len(adj)
L, R, D, P = [0]*N, [0]*N, [0]*N, [[] for _ in xrange(N)]
idx = -1
stk = [(1, (0, -1))]
while stk:
step, args = stk.pop()
if step == 1:
u, p = args
D[u] = 1 if p == -1 else D[p]+1
if p != -1:
P[u].append(p)
i = 0
while i < len(P[u]) and i < len(P[P[u][i]]):
P[u].append(P[P[u][i]][i])
i += 1
idx += 1
L[u] = idx
stk.append((2, (u,)))
for i in reversed(xrange(len(adj[u]))):
v = adj[u][i]
if v == p:
continue
stk.append((1, (v, u)))
elif step == 2:
u = args[0]
R[u] = idx
assert(idx == N-1)
self.L, self.R, self.D, self.P = L, R, D, P
# Template:
# https://github.com/kamyu104/FacebookHackerCup-2019/blob/master/Final%20Round/little_boat_on_the_sea.py
def is_ancestor(self, a, b): # includes itself
return self.L[a] <= self.L[b] <= self.R[b] <= self.R[a]
def lca(self, a, b):
if self.D[a] > self.D[b]:
a, b = b, a
if self.is_ancestor(a, b):
return a
for i in reversed(xrange(len(self.P[a]))): # O(logN)
if i < len(self.P[a]) and not self.is_ancestor(self.P[a][i], b):
a = self.P[a][i]
return self.P[a][0]
s = list(s)
adj = [[] for _ in xrange(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
tree_infos = TreeInfos(adj)
bit = BIT(n+1)
for u in xrange(n):
diff = 1<<(ord(s[u])-ord('a'))
bit.add(tree_infos.L[u], diff)
bit.add(tree_infos.R[u]+1, diff)
result = []
for q in queries:
args = q.split()
op = args[0]
u = int(args[1])
if op == "update":
c = args[2]
diff = (1<<(ord(s[u])-ord('a')))^(1<<(ord(c)-ord('a')))
if not diff:
continue
s[u] = c
bit.add(tree_infos.L[u], diff)
bit.add(tree_infos.R[u]+1, diff)
else:
v = int(args[2])
l = tree_infos.lca(u, v)
mask = bit.query(tree_infos.L[u])^bit.query(tree_infos.L[v])^(1<<(ord(s[l])-ord('a')))
result.append(mask == 0 or (mask&(mask-1)) == 0)
return result
// Accepted solution for LeetCode #3841: Palindromic Path Queries in a Tree
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3841: Palindromic Path Queries in a Tree
// package main
//
// import (
// "math/bits"
// "strconv"
// "strings"
// )
//
// // https://space.bilibili.com/206214
// // 模板来自我的题单 https://leetcode.cn/circle/discuss/mOr1u6/
// type fenwick []int
//
// func newFenwickTree(n int) fenwick {
// return make(fenwick, n+1) // 使用下标 1 到 n
// }
//
// // a[i] ^= val
// // 1 <= i <= n
// // 时间复杂度 O(log n)
// func (f fenwick) update(i int, val int) {
// for ; i < len(f); i += i & -i {
// f[i] ^= val
// }
// }
//
// // 计算前缀异或和 a[1] ^ ... ^ a[i]
// // 1 <= i <= n
// // 时间复杂度 O(log n)
// func (f fenwick) pre(i int) (res int) {
// for ; i > 0; i &= i - 1 {
// res ^= f[i]
// }
// return
// }
//
// func palindromePath(n int, edges [][]int, s string, queries []string) (ans []bool) {
// g := make([][]int, n)
// for _, e := range edges {
// x, y := e[0], e[1]
// g[x] = append(g[x], y)
// g[y] = append(g[y], x)
// }
//
// mx := bits.Len(uint(n))
// pa := make([][16]int, n)
// dep := make([]int, n)
// timeIn := make([]int, n) // DFS 时间戳
// timeOut := make([]int, n)
// clock := 0
// pathXorFromRoot := make([]int, n) // 从根开始的路径中的字母奇偶性的集合
// pathXorFromRoot[0] = 1 << (s[0] - 'a')
//
// var dfs func(int, int)
// dfs = func(x, p int) {
// pa[x][0] = p
// clock++
// timeIn[x] = clock
// for _, y := range g[x] {
// if y != p {
// dep[y] = dep[x] + 1
// pathXorFromRoot[y] = pathXorFromRoot[x] ^ 1<<(s[y]-'a')
// dfs(y, x)
// }
// }
// timeOut[x] = clock
// }
// dfs(0, -1)
//
// for i := range mx - 1 {
// for x := range pa {
// p := pa[x][i]
// if p != -1 {
// pa[x][i+1] = pa[p][i]
// } else {
// pa[x][i+1] = -1
// }
// }
// }
//
// uptoDep := func(x, d int) int {
// for k := uint32(dep[x] - d); k > 0; k &= k - 1 {
// x = pa[x][bits.TrailingZeros32(k)]
// }
// return x
// }
//
// // 返回 x 和 y 的最近公共祖先
// getLCA := func(x, y int) int {
// if dep[x] > dep[y] {
// x, y = y, x
// }
// y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
// if y == x {
// return x
// }
// for i := mx - 1; i >= 0; i-- {
// px, py := pa[x][i], pa[y][i]
// if px != py {
// x, y = px, py // 同时往上跳 2^i 步
// }
// }
// return pa[x][0]
// }
//
// // 上面全是模板，下面开始本题逻辑
//
// t := []byte(s)
// f := newFenwickTree(n) // 注意树状数组是异或运算
// for _, q := range queries {
// if q[0] == 'u' {
// x, _ := strconv.Atoi(q[7 : len(q)-2])
// c := q[len(q)-1]
// val := 1<<(t[x]-'a') ^ 1<<(c-'a') // 擦除旧的，换上新的
// t[x] = c
// // 子树 x 全部异或 val，转换成对区间 [timeIn[x], timeOut[x]] 的差分更新
// f.update(timeIn[x], val)
// f.update(timeOut[x]+1, val)
// } else {
// q = q[6:]
// i := strings.IndexByte(q, ' ')
// x, _ := strconv.Atoi(q[:i])
// y, _ := strconv.Atoi(q[i+1:])
// lca := getLCA(x, y)
// res := pathXorFromRoot[x] ^ pathXorFromRoot[y] ^ f.pre(timeIn[x]) ^ f.pre(timeIn[y]) ^ 1<<(t[lca]-'a')
// ans = append(ans, res&(res-1) == 0) // 至多一个字母的出现次数是奇数
// }
// }
// return
// }
// Accepted solution for LeetCode #3841: Palindromic Path Queries in a Tree
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3841: Palindromic Path Queries in a Tree
// package main
//
// import (
// "math/bits"
// "strconv"
// "strings"
// )
//
// // https://space.bilibili.com/206214
// // 模板来自我的题单 https://leetcode.cn/circle/discuss/mOr1u6/
// type fenwick []int
//
// func newFenwickTree(n int) fenwick {
// return make(fenwick, n+1) // 使用下标 1 到 n
// }
//
// // a[i] ^= val
// // 1 <= i <= n
// // 时间复杂度 O(log n)
// func (f fenwick) update(i int, val int) {
// for ; i < len(f); i += i & -i {
// f[i] ^= val
// }
// }
//
// // 计算前缀异或和 a[1] ^ ... ^ a[i]
// // 1 <= i <= n
// // 时间复杂度 O(log n)
// func (f fenwick) pre(i int) (res int) {
// for ; i > 0; i &= i - 1 {
// res ^= f[i]
// }
// return
// }
//
// func palindromePath(n int, edges [][]int, s string, queries []string) (ans []bool) {
// g := make([][]int, n)
// for _, e := range edges {
// x, y := e[0], e[1]
// g[x] = append(g[x], y)
// g[y] = append(g[y], x)
// }
//
// mx := bits.Len(uint(n))
// pa := make([][16]int, n)
// dep := make([]int, n)
// timeIn := make([]int, n) // DFS 时间戳
// timeOut := make([]int, n)
// clock := 0
// pathXorFromRoot := make([]int, n) // 从根开始的路径中的字母奇偶性的集合
// pathXorFromRoot[0] = 1 << (s[0] - 'a')
//
// var dfs func(int, int)
// dfs = func(x, p int) {
// pa[x][0] = p
// clock++
// timeIn[x] = clock
// for _, y := range g[x] {
// if y != p {
// dep[y] = dep[x] + 1
// pathXorFromRoot[y] = pathXorFromRoot[x] ^ 1<<(s[y]-'a')
// dfs(y, x)
// }
// }
// timeOut[x] = clock
// }
// dfs(0, -1)
//
// for i := range mx - 1 {
// for x := range pa {
// p := pa[x][i]
// if p != -1 {
// pa[x][i+1] = pa[p][i]
// } else {
// pa[x][i+1] = -1
// }
// }
// }
//
// uptoDep := func(x, d int) int {
// for k := uint32(dep[x] - d); k > 0; k &= k - 1 {
// x = pa[x][bits.TrailingZeros32(k)]
// }
// return x
// }
//
// // 返回 x 和 y 的最近公共祖先
// getLCA := func(x, y int) int {
// if dep[x] > dep[y] {
// x, y = y, x
// }
// y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
// if y == x {
// return x
// }
// for i := mx - 1; i >= 0; i-- {
// px, py := pa[x][i], pa[y][i]
// if px != py {
// x, y = px, py // 同时往上跳 2^i 步
// }
// }
// return pa[x][0]
// }
//
// // 上面全是模板，下面开始本题逻辑
//
// t := []byte(s)
// f := newFenwickTree(n) // 注意树状数组是异或运算
// for _, q := range queries {
// if q[0] == 'u' {
// x, _ := strconv.Atoi(q[7 : len(q)-2])
// c := q[len(q)-1]
// val := 1<<(t[x]-'a') ^ 1<<(c-'a') // 擦除旧的，换上新的
// t[x] = c
// // 子树 x 全部异或 val，转换成对区间 [timeIn[x], timeOut[x]] 的差分更新
// f.update(timeIn[x], val)
// f.update(timeOut[x]+1, val)
// } else {
// q = q[6:]
// i := strings.IndexByte(q, ' ')
// x, _ := strconv.Atoi(q[:i])
// y, _ := strconv.Atoi(q[i+1:])
// lca := getLCA(x, y)
// res := pathXorFromRoot[x] ^ pathXorFromRoot[y] ^ f.pre(timeIn[x]) ^ f.pre(timeIn[y]) ^ 1<<(t[lca]-'a')
// ans = append(ans, res&(res-1) == 0) // 至多一个字母的出现次数是奇数
// }
// }
// return
// }
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.