You are given a tree with N nodes numbered 0..N-1. Each node holds the letter 'a' or 'b'. The tree is described by an array A of length N where A[k] is the parent of node k, with A[root] = -1. Letters are stored in a string S (S[k] is the letter of node k). Return the number of vertices on the longest path such that no two adjacent nodes on the path share the same letter.
Example
solution("ab", [-1, 0]) = 2
solution("abbab", [-1, 0, 0, 0, 2]) = 3For S = "abbab", A = [-1, 0, 0, 0, 2], the longest alternating path is 1 — 0 — 2.
解法
树根固定后，节点 u DFS 每个孩子 v：取 v 处最长向下链；若 S[v] != S[u] 则可挂到 u。在 u 处合并最长的两条链更新答案(经过 u 的路径)，返回 top1 + 1 给父亲。复杂度 O(N)。
import sys
from collections import defaultdict
def solution(S: str, A: list[int]) -> int:
n = len(A)
if n == 1:
return 1
sys.setrecursionlimit(n + 100)
children = defaultdict(list)
root = -1
for v, p in enumerate(A):
if p == -1:
root = v
else:
children[p].append(v)
ans = 1
def dfs(u: int) -> int:
# returns longest valid chain ending at u (inclusive), extending downward
nonlocal ans
downs = []
for v in children[u]:
child_chain = dfs(v)
if S[v] != S[u]:
downs.append(child_chain)
downs.sort(reverse=True)
top1 = downs[0] if len(downs) >= 1 else 0
top2 = downs[1] if len(downs) >= 2 else 0
ans = max(ans, top1 + top2 + 1)
return top1 + 1
dfs(root)
return ansimport java.util.*;
class Solution {
String s;
List<List<Integer>> children;
int ans;
int solution(String S, int[] A) {
int n = A.length;
if (n == 1) return 1;
this.s = S;
this.children = new ArrayList<>();
for (int i = 0; i < n; i++) children.add(new ArrayList<>());
int root = -1;
for (int v = 0; v < n; v++) {
if (A[v] == -1) root = v;
else children.get(A[v]).add(v);
}
ans = 1;
dfs(root);
return ans;
}
// returns longest valid chain ending at u (inclusive)
int dfs(int u) {
List<Integer> downs = new ArrayList<>();
for (int v : children.get(u)) {
int childChain = dfs(v);
if (s.charAt(v) != s.charAt(u)) {
downs.add(childChain);
}
}
downs.sort(Collections.reverseOrder());
int top1 = downs.size() >= 1 ? downs.get(0) : 0;
int top2 = downs.size() >= 2 ? downs.get(1) : 0;
ans = Math.max(ans, top1 + top2 + 1);
return top1 + 1;
}
}#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
string s;
vector<vector<int>> children;
int ans;
int solution(string S, vector<int>& A) {
int n = A.size();
if (n == 1) return 1;
s = S;
children.assign(n, {});
int root = -1;
for (int v = 0; v < n; v++) {
if (A[v] == -1) root = v;
else children[A[v]].push_back(v);
}
ans = 1;
dfs(root);
return ans;
}
// returns longest valid chain ending at u (inclusive)
int dfs(int u) {
vector<int> downs;
for (int v : children[u]) {
int childChain = dfs(v);
if (s[v] != s[u]) downs.push_back(childChain);
}
sort(downs.begin(), downs.end(), greater<int>());
int top1 = downs.size() >= 1 ? downs[0] : 0;
int top2 = downs.size() >= 2 ? downs[1] : 0;
ans = max(ans, top1 + top2 + 1);
return top1 + 1;
}
};You are given two arrays A and B, each of length N. Build array C where for each index k, C[k] is either A[k] or B[k]. Choose values so the smallest positive integer missing from C is as small as possible — i.e. return the smallest positive integer that cannot occur in any merged C.
Example
solution([1, 2, 4, 3], [1, 3, 2, 3]) = 2
solution([3, 2, 1, 6, 5], [4, 2, 1, 3, 3]) = 3
solution([1, 2], [1, 2]) = 3Constraints
1 ≤ N ≤ 10⁵, 1 ≤ A[i], B[i] ≤ 10⁵.
解法
建二分图：整数 v(1..N+1)连向 A 或 B 中包含 v 的下标。按 1, 2, ... 顺序用增广路(匈牙利算法)贪心匹配到不同下标，首个无法匹配的整数即答案。最坏 O(N²)，随机输入很快。
from collections import defaultdict
def solution(A: list[int], B: list[int]) -> int:
n = len(A)
positions = defaultdict(list)
for k in range(n):
positions[A[k]].append(k)
if B[k] != A[k]:
positions[B[k]].append(k)
used = [None] * n
assigned = {}
def try_assign(v: int, visited: set) -> bool:
for k in positions[v]:
if k in visited:
continue
visited.add(k)
if used[k] is None or try_assign(used[k], visited):
used[k] = v
assigned[v] = k
return True
return False
for v in range(1, n + 2):
if v not in positions:
return v
if not try_assign(v, set()):
return v
return n + 1import java.util.*;
class Solution {
Map<Integer, List<Integer>> positions;
Integer[] used;
int solution(int[] A, int[] B) {
int n = A.length;
positions = new HashMap<>();
for (int k = 0; k < n; k++) {
positions.computeIfAbsent(A[k], x -> new ArrayList<>()).add(k);
if (B[k] != A[k]) {
positions.computeIfAbsent(B[k], x -> new ArrayList<>()).add(k);
}
}
used = new Integer[n];
for (int v = 1; v <= n + 1; v++) {
if (!positions.containsKey(v)) return v;
Set<Integer> visited = new HashSet<>();
if (!tryAssign(v, visited)) return v;
}
return n + 1;
}
boolean tryAssign(int v, Set<Integer> visited) {
for (int k : positions.get(v)) {
if (visited.contains(k)) continue;
visited.add(k);
if (used[k] == null || tryAssign(used[k], visited)) {
used[k] = v;
return true;
}
}
return false;
}
}#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
unordered_map<int, vector<int>> positions;
vector<int> used;
int solution(vector<int>& A, vector<int>& B) {
int n = A.size();
positions.clear();
for (int k = 0; k < n; k++) {
positions[A[k]].push_back(k);
if (B[k] != A[k]) positions[B[k]].push_back(k);
}
used.assign(n, -1);
for (int v = 1; v <= n + 1; v++) {
if (positions.find(v) == positions.end()) return v;
unordered_set<int> visited;
if (!tryAssign(v, visited)) return v;
}
return n + 1;
}
bool tryAssign(int v, unordered_set<int>& visited) {
for (int k : positions[v]) {
if (visited.count(k)) continue;
visited.insert(k);
if (used[k] == -1 || tryAssign(used[k], visited)) {
used[k] = v;
return true;
}
}
return false;
}
};You are given a string S. In one move you can erase any pair of identical letters from S. Find the shortest possible string achievable; among all such shortest strings, return the lexicographically smallest one.
Example
solution("CBCAAXA") = "BAX"
solution("ZYXZYZYV") = "XYZV" // length 4 cannot be shortened further with this exact spec
solution("ABCBACDDAB") = ""
solution("AKFKFNOGKFB") = "AFKMOGB"Constraints
1 ≤ N ≤ 10⁵, S consists of uppercase letters.
解法
消除所有重复对后，偶数次出现的字母全部消失，奇数次出现的字母各保留一份。在所有合法顺序中取字典序最小：经典单调栈，从左到右扫，若栈顶大于当前字符且后面还有同样的字符就弹出。复杂度 O(N)。
def solution(S: str) -> str:
n = len(S)
total = [0] * 26
for c in S:
total[ord(c) - ord('A')] += 1
# target[ch] = 1 means this letter must be kept exactly once
target = [t % 2 for t in total]
seen = [0] * 26
in_stack = [False] * 26
stack = []
for i, c in enumerate(S):
idx = ord(c) - ord('A')
seen[idx] += 1
if target[idx] == 0:
continue
if in_stack[idx]:
continue
# pop a larger top if the same letter still appears later
while stack and stack[-1] > c:
top_idx = ord(stack[-1]) - ord('A')
remaining = total[top_idx] - seen[top_idx]
if remaining >= 1:
stack.pop()
in_stack[top_idx] = False
else:
break
stack.append(c)
in_stack[idx] = True
return ''.join(stack)class Solution {
String solution(String S) {
int n = S.length();
int[] total = new int[26];
for (char c : S.toCharArray()) total[c - 'A']++;
int[] target = new int[26];
for (int i = 0; i < 26; i++) target[i] = total[i] % 2;
int[] seen = new int[26];
boolean[] inStack = new boolean[26];
StringBuilder stack = new StringBuilder();
for (int i = 0; i < n; i++) {
char c = S.charAt(i);
int idx = c - 'A';
seen[idx]++;
if (target[idx] == 0) continue;
if (inStack[idx]) continue;
while (stack.length() > 0 && stack.charAt(stack.length() - 1) > c) {
char top = stack.charAt(stack.length() - 1);
int topIdx = top - 'A';
int remaining = total[topIdx] - seen[topIdx];
if (remaining >= 1) {
stack.deleteCharAt(stack.length() - 1);
inStack[topIdx] = false;
} else {
break;
}
}
stack.append(c);
inStack[idx] = true;
}
return stack.toString();
}
}#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string solution(string S) {
int n = S.size();
vector<int> total(26, 0);
for (char c : S) total[c - 'A']++;
vector<int> target(26);
for (int i = 0; i < 26; i++) target[i] = total[i] % 2;
vector<int> seen(26, 0);
vector<bool> inStack(26, false);
string stk;
for (int i = 0; i < n; i++) {
char c = S[i];
int idx = c - 'A';
seen[idx]++;
if (target[idx] == 0) continue;
if (inStack[idx]) continue;
while (!stk.empty() && stk.back() > c) {
char top = stk.back();
int topIdx = top - 'A';
int remaining = total[topIdx] - seen[topIdx];
if (remaining >= 1) {
stk.pop_back();
inStack[topIdx] = false;
} else {
break;
}
}
stk.push_back(c);
inStack[idx] = true;
}
return stk;
}
};