# Final Character ## Solution 1: Direct Simulation by String Manipulation ### Intuition The most straightforward way to solve this problem is to directly simulate the game as described. In each turn, we can determine the current player's best move by generating all possible outcomes and choosing the one that is lexicographically smallest (for Alex) or largest (for Charlie). - For each turn, we iterate through every character of the current string. - Removing each character one by one gives us a set of possible next strings. - Alex will choose the string that comes first alphabetically. - Charlie will choose the string that comes last alphabetically. - We repeat this process until only one character is left. This approach is correct because it exhaustively checks every option for the greedy players, but it will be very slow due to repeated string creation and comparison. ### Approach - Start with the initial string `S`. - Loop for `|S| - 1` turns, which is the total number of characters to be removed. - In each turn, determine if it's Alex's or Charlie's move based on the turn number (Alex starts at turn 0, even turns). - Generate all possible strings that can be formed by removing a single character from the current string. - If it's Alex's turn, find the lexicographically smallest string among the generated strings. - If it's Charlie's turn, find the lexicographically largest one. - Update the current string to be the one chosen by the player. - After the loop finishes, the string will have a single character. Return this character. ### Pseudocode ```pseudocode function finalCharacter(S) { /* Convert string to a list of characters for easier manipulation */ current_chars = list(S) num_removals = length(S) - 1 /* Simulate the game for the total number of removals */ for turn = 0 to num_removals - 1 { best_next_string = "" /* Alex's turn (minimize) */ if turn is even { /* Initialize with a very large string */ best_next_string = "z" * (length(current_chars) - 1) /* Generate all possible next strings by removing one character */ for i = 0 to length(current_chars) - 1 { temp_chars = copy(current_chars) remove temp_chars[i] /* Convert back to string for comparison */ temp_string = join(temp_chars) /* If this move is better, update the best string */ if temp_string < best_next_string { best_next_string = temp_string } } } /* Charlie's turn (maximize) */ else { /* Initialize with a very small string */ best_next_string = "a" * (length(current_chars) - 1) /* Generate all possible next strings */ for i = 0 to length(current_chars) - 1 { temp_chars = copy(current_chars) remove temp_chars[i] temp_string = join(temp_chars) /* If this move is better, update the best string */ if temp_string > best_next_string { best_next_string = temp_string } } } /* Update the list of characters for the next turn */ current_chars = list(best_next_string) } /* The final list contains one character */ return current_chars[0] } ``` ### Code Implementation ```cpp #include #include #include #include class solution { public: char finalCharacter(std::string S) { std::string current_s = S; int n = S.length(); for (int turn = 0; turn < n - 1; ++turn) { std::string best_next_s = ""; int len = current_s.length(); if (turn % 2 == 0) { // Alex's turn (minimize) for (int i = 0; i < len; ++i) { std::string temp_s = current_s.substr(0, i) + current_s.substr(i + 1); if (best_next_s == "" || temp_s < best_next_s) { best_next_s = temp_s; } } } else { // Charlie's turn (maximize) for (int i = 0; i < len; ++i) { std::string temp_s = current_s.substr(0, i) + current_s.substr(i + 1); if (best_next_s == "" || temp_s > best_next_s) { best_next_s = temp_s; } } } current_s = best_next_s; } return current_s[0]; } }; /* int main() { std::string s; std::cin >> s; solution sol; char result = sol.finalCharacter(s); std::cout << result << std::endl; return 0; } */ ``` ```python import sys class solution: def finalCharacter(self, S: str) -> str: current_s = S n = len(S) for turn in range(n - 1): best_next_s = "" if turn % 2 == 0: # Alex's turn (minimize) for i in range(len(current_s)): temp_s = current_s[:i] + current_s[i+1:] if best_next_s == "" or temp_s < best_next_s: best_next_s = temp_s else: # Charlie's turn (maximize) for i in range(len(current_s)): temp_s = current_s[:i] + current_s[i+1:] if best_next_s == "" or temp_s > best_next_s: best_next_s = temp_s current_s = best_next_s return current_s[0] ''' s = sys.stdin.readline().strip() sol = solution() result = sol.finalCharacter(s) print(result) ''' ``` ```java import java.util.Scanner; class Solution { public static char finalCharacter(String S) { String currentS = S; int n = S.length(); for (int turn = 0; turn < n - 1; turn++) { String bestNextS = ""; int len = currentS.length(); if (turn % 2 == 0) { // Alex's turn (minimize) for (int i = 0; i < len; i++) { StringBuilder sb = new StringBuilder(currentS); sb.deleteCharAt(i); String tempS = sb.toString(); if (bestNextS.isEmpty() || tempS.compareTo(bestNextS) < 0) { bestNextS = tempS; } } } else { // Charlie's turn (maximize) for (int i = 0; i < len; i++) { StringBuilder sb = new StringBuilder(currentS); sb.deleteCharAt(i); String tempS = sb.toString(); if (bestNextS.isEmpty() || tempS.compareTo(bestNextS) > 0) { bestNextS = tempS; } } } currentS = bestNextS; } return currentS.charAt(0); } } /* public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.next(); char result = Solution.finalCharacter(s); System.out.println(result); } } */ ``` ```javascript class Solution { static finalCharacter(S) { let currentS = S; const n = S.length; for (let turn = 0; turn < n - 1; turn++) { let bestNextS = ""; const len = currentS.length; if (turn % 2 === 0) { // Alex's turn (minimize) for (let i = 0; i < len; i++) { const tempS = currentS.substring(0, i) + currentS.substring(i + 1); if (bestNextS === "" || tempS < bestNextS) { bestNextS = tempS; } } } else { // Charlie's turn (maximize) for (let i = 0; i < len; i++) { const tempS = currentS.substring(0, i) + currentS.substring(i + 1); if (bestNextS === "" || tempS > bestNextS) { bestNextS = tempS; } } } currentS = bestNextS; } return currentS[0]; } } /* function main() { const fs = require("fs"); const s = fs.readFileSync(0, "utf8").trim(); const result = Solution.finalCharacter(s); console.log(result); } main(); */ ``` ### Complexity Analysis - **Time Complexity:** `O(N^3)` — The main loop runs `N-1` times, inside we generate and compare strings of length `k` which takes `O(k)` per iteration, leading to `O(N^3)` total. - **Space Complexity:** `O(N)` — We store the current string and temporary strings. ## Solution 2: Greedy Simulation with Linear Scan ### Intuition The direct simulation is slow because it generates and compares many strings. We can optimize this by finding a greedy strategy for each player. - To make a string lexicographically smallest, we want to make its prefix as small as possible. The best way to do this is to find the first character from the left, `S[i]`, that is greater than its neighbor, `S[i+1]`. Removing `S[i]` replaces it with `S[i+1]`, making the prefix smaller. If the string is already sorted non-decreasingly (e.g., "aabc"), removing the last (largest) character is the optimal move. - Similarly, to make a string largest, Charlie should find the first character `S[i]` that is smaller than `S[i+1]` and remove it. If the string is sorted non-increasingly (e.g., "dcba"), he should remove the last (smallest) character. This greedy approach avoids generating all possible strings and directly identifies the single best character to remove in each turn. ### Approach - Start with the initial string `S`. - Loop for `|S| - 1` turns. - In each turn, determine the player. - **If it's Alex's turn (minimize):** - Scan the string from left to right to find the first index `i` where `S[i] > S[i+1]`. - If such an index is found, remove the character at `i`. - If no such index is found (the string is sorted), remove the last character. - **If it's Charlie's turn (maximize):** - Scan the string to find the first index `i` where `S[i] < S[i+1]`. - If found, remove the character at `i`. - If not found (string is reverse-sorted), remove the last character. - Update the string after each removal. - After the loop, return the single remaining character. ### Pseudocode ```pseudocode function finalCharacter(S) { /* Use a mutable list of characters */ current_chars = list(S) num_removals = length(S) - 1 for turn = 0 to num_removals - 1 { len = length(current_chars) removal_index = -1 /* Alex's turn (minimize) */ if turn is even { /* Find first character S[i] > S[i+1] */ for i = 0 to len - 2 { if current_chars[i] > current_chars[i+1] { removal_index = i break } } /* If string is sorted, remove the last character */ if removal_index == -1 { removal_index = len - 1 } } /* Charlie's turn (maximize) */ else { /* Find first character S[i] < S[i+1] */ for i = 0 to len - 2 { if current_chars[i] < current_chars[i+1] { removal_index = i break } } /* If string is reverse-sorted, remove the last character */ if removal_index == -1 { removal_index = len - 1 } } /* Remove the chosen character */ remove current_chars[removal_index] } /* Return the final character */ return current_chars[0] } ``` ### Code Implementation ```cpp #include #include #include #include class solution { public: char finalCharacter(std::string S) { std::string current_s = S; int n = S.length(); for (int turn = 0; turn < n - 1; ++turn) { int len = current_s.length(); int removal_idx = -1; if (turn % 2 == 0) { // Alex's turn (minimize) for (int i = 0; i < len - 1; ++i) { if (current_s[i] > current_s[i + 1]) { removal_idx = i; break; } } if (removal_idx == -1) { removal_idx = len - 1; } } else { // Charlie's turn (maximize) for (int i = 0; i < len - 1; ++i) { if (current_s[i] < current_s[i + 1]) { removal_idx = i; break; } } if (removal_idx == -1) { removal_idx = len - 1; } } current_s.erase(removal_idx, 1); } return current_s[0]; } }; /* int main() { std::string s; std::cin >> s; solution sol; char result = sol.finalCharacter(s); std::cout << result << std::endl; return 0; } */ ``` ```python import sys class solution: def finalCharacter(self, S: str) -> str: chars = list(S) n = len(S) for turn in range(n - 1): removal_idx = -1 if turn % 2 == 0: # Alex's turn (minimize) for i in range(len(chars) - 1): if chars[i] > chars[i+1]: removal_idx = i break if removal_idx == -1: removal_idx = len(chars) - 1 else: # Charlie's turn (maximize) for i in range(len(chars) - 1): if chars[i] < chars[i+1]: removal_idx = i break if removal_idx == -1: removal_idx = len(chars) - 1 chars.pop(removal_idx) return chars[0] ''' s = sys.stdin.readline().strip() sol = solution() result = sol.finalCharacter(s) print(result) ''' ``` ```java import java.util.Scanner; import java.util.ArrayList; import java.util.List; class Solution { public static char finalCharacter(String S) { StringBuilder currentS = new StringBuilder(S); int n = S.length(); for (int turn = 0; turn < n - 1; turn++) { int len = currentS.length(); int removalIdx = -1; if (turn % 2 == 0) { // Alex's turn (minimize) for (int i = 0; i < len - 1; i++) { if (currentS.charAt(i) > currentS.charAt(i + 1)) { removalIdx = i; break; } } if (removalIdx == -1) { removalIdx = len - 1; } } else { // Charlie's turn (maximize) for (int i = 0; i < len - 1; i++) { if (currentS.charAt(i) < currentS.charAt(i + 1)) { removalIdx = i; break; } } if (removalIdx == -1) { removalIdx = len - 1; } } currentS.deleteCharAt(removalIdx); } return currentS.charAt(0); } } /* public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.next(); char result = Solution.finalCharacter(s); System.out.println(result); } } */ ``` ```javascript class Solution { static finalCharacter(S) { let chars = S.split(''); const n = S.length; for (let turn = 0; turn < n - 1; turn++) { let removalIdx = -1; const len = chars.length; if (turn % 2 === 0) { // Alex's turn (minimize) for (let i = 0; i < len - 1; i++) { if (chars[i] > chars[i + 1]) { removalIdx = i; break; } } if (removalIdx === -1) { removalIdx = len - 1; } } else { // Charlie's turn (maximize) for (let i = 0; i < len - 1; i++) { if (chars[i] < chars[i + 1]) { removalIdx = i; break; } } if (removalIdx === -1) { removalIdx = len - 1; } } chars.splice(removalIdx, 1); } return chars[0]; } } /* function main() { const fs = require("fs"); const s = fs.readFileSync(0, "utf8").trim(); const result = Solution.finalCharacter(s); console.log(result); } main(); */ ``` ### Complexity Analysis - **Time Complexity:** `O(N^2)` — The main loop runs `N-1` times, each involving a linear scan and a removal that takes `O(k)` time, resulting in `O(N^2)` total. - **Space Complexity:** `O(N)` — We store the current string or list of characters. ## Solution 3: Optimized Simulation using a Doubly Linked List and Priority Queues ### Intuition The `O(N^2)` greedy simulation is slow because both finding the removal index (linear scan) and performing the removal (shifting elements) take linear time. We can optimize both operations. - **To optimize removal:** A doubly linked list allows character removal in `O(1)` time if we have a pointer to the node. - **To optimize finding the index:** Instead of scanning the entire list every turn, we can pre-calculate all locations where a player would want to make a move. For Alex, these are "peaks" (where `S[i] > S[i+1]`), and for Charlie, "valleys" (where `S[i] < S[i+1]`). We can store these locations in a data structure that gives us the first one (smallest index) quickly. A priority queue (min-heap) or an ordered set is perfect for this, providing the minimum index in `O(log K)` time, where `K` is the number of peaks/valleys. By combining these data structures, we can reduce the time per turn from `O(N)` to `O(log N)`, leading to an efficient overall solution. ### Approach - **Initialization:** - Represent the string as a doubly linked list, where each node stores a character and its original index. - Create two min-priority queues, `peaks` and `valleys`, to store pairs of `(original_index, node_pointer)`. - Traverse the initial linked list and populate `peaks` with nodes `u` where `u.val > u.next.val` and `valleys` with nodes `u` where `u.val < u.next.val`. - **Game Simulation:** - Loop `|S| - 1` times. - **Alex's turn (minimize):** - If `peaks` is not empty, get the node with the smallest index from `peaks`. - If `peaks` is empty (string is sorted), choose the tail of the linked list. - **Charlie's turn (maximize):** - If `valleys` is not empty, get the node with the smallest index from `valleys`. - If `valleys` is empty (string is reverse-sorted), choose the tail. - **Update:** - Let the chosen node be `u`, its predecessor `p`, and successor `n`. - Before removing `u`, we must invalidate any peak/valley information related to `p` and `u`, as their adjacencies will change. We can do this with lazy deletion in the priority queue or by explicitly removing them from sets. - Remove `u` by linking `p` and `n` directly (`p.next = n`, `n.prev = p`). This is an `O(1)` operation. - After removal, a new adjacency between `p` and `n` is formed. Check if this new pair creates a new peak or valley at `p` and update the priority queues accordingly. - After the loop, the linked list contains one node. Return its character. ### Pseudocode ```pseudocode /* Node structure for the Doubly Linked List */ Node { char val int id /* original index */ Node prev, next } function finalCharacter(S) { /* 1. Initialization */ N = length(S) if N <= 1 return S[0] /* Create Doubly Linked List */ nodes = array of N Nodes for i = 0 to N-1 { nodes[i].val = S[i], nodes[i].id = i if i > 0, nodes[i].prev = &nodes[i-1] if i < N-1, nodes[i].next = &nodes[i+1] } head = &nodes[0], tail = &nodes[N-1] /* Create and populate priority queues for peaks and valleys */ peaks_pq = min_priority_queue() valleys_pq = min_priority_queue() for i = 0 to N-2 { if nodes[i].val > nodes[i+1].val { peaks_pq.push({nodes[i].id, &nodes[i]}) } else if nodes[i].val < nodes[i+1].val { valleys_pq.push({nodes[i].id, &nodes[i]}) } } /* Keep track of active nodes to handle lazy deletion */ active_nodes = set of all node ids /* 2. Game Simulation */ for turn = 0 to N-2 { node_to_remove = null /* Alex's turn */ if turn is even { /* Find a valid peak from the priority queue */ while not peaks_pq.empty() and peaks_pq.top().id not in active_nodes { peaks_pq.pop() } if not peaks_pq.empty() { node_to_remove = peaks_pq.top().node peaks_pq.pop() } else { node_to_remove = tail } } /* Charlie's turn */ else { /* Find a valid valley from the priority queue */ while not valleys_pq.empty() and valleys_pq.top().id not in active_nodes { valleys_pq.pop() } if not valleys_pq.empty() { node_to_remove = valleys_pq.top().node valleys_pq.pop() } else { node_to_remove = tail } } /* 3. Update Data Structures */ p = node_to_remove.prev n = node_to_remove.next /* Mark node as inactive for lazy deletion */ active_nodes.remove(node_to_remove.id) if p is not null, active_nodes.remove(p.id) /* p's relation changes */ /* Relink the list */ if p is not null, p.next = n else, head = n if n is not null, n.prev = p else, tail = p /* Re-evaluate p's new relation and add back to active set and PQs if needed */ if p is not null { active_nodes.add(p.id) if p.next is not null { if p.val > p.next.val, peaks_pq.push({p.id, p}) else if p.val < p.next.val, valleys_pq.push({p.id, p}) } } } /* Return the last remaining character */ return head.val } ``` ### Code Implementation ```cpp #include #include #include #include #include struct Node { char val; int id; Node* prev = nullptr; Node* next = nullptr; }; struct NodeInfo { int id; Node* node; bool operator>(const NodeInfo& other) const { return id > other.id; } }; class solution { public: char finalCharacter(std::string S) { int n = S.length(); if (n <= 1) { return S[0]; } std::vector nodes(n); for (int i = 0; i < n; ++i) { nodes[i].val = S[i]; nodes[i].id = i; if (i > 0) nodes[i].prev = &nodes[i - 1]; if (i < n - 1) nodes[i].next = &nodes[i + 1]; } Node* head = &nodes[0]; Node* tail = &nodes[n - 1]; std::priority_queue, std::greater> peaks, valleys; std::set active_ids; for (int i = 0; i < n; ++i) { active_ids.insert(i); } for (int i = 0; i < n - 1; ++i) { if (nodes[i].val > nodes[i + 1].val) { peaks.push({nodes[i].id, &nodes[i]}); } else if (nodes[i].val < nodes[i + 1].val) { valleys.push({nodes[i].id, &nodes[i]}); } } for (int turn = 0; turn < n - 1; ++turn) { Node* to_remove = nullptr; if (turn % 2 == 0) { // Alex while (!peaks.empty() && active_ids.find(peaks.top().id) == active_ids.end()) { peaks.pop(); } if (!peaks.empty()) { to_remove = peaks.top().node; peaks.pop(); } else { to_remove = tail; } } else { // Charlie while (!valleys.empty() && active_ids.find(valleys.top().id) == active_ids.end()) { valleys.pop(); } if (!valleys.empty()) { to_remove = valleys.top().node; valleys.pop(); } else { to_remove = tail; } } active_ids.erase(to_remove->id); Node* p = to_remove->prev; Node* n_node = to_remove->next; if (p) { p->next = n_node; } else { head = n_node; } if (n_node) { n_node->prev = p; } else { tail = p; } if (p) { if (p->next) { if (p->val > p->next->val) { peaks.push({p->id, p}); } else if (p->val < p->next->val) { valleys.push({p->id, p}); } } } } return head->val; } }; /* int main() { std::string s; std::cin >> s; solution sol; char result = sol.finalCharacter(s); std::cout << result << std::endl; return 0; } */ ``` ```python import heapq class Node: def __init__(self, val, id): self.val = val self.id = id self.prev = None self.next = None class solution: def finalCharacter(self, S: str) -> str: n = len(S) if n <= 1: return S[0] nodes = [Node(S[i], i) for i in range(n)] for i in range(n): if i > 0: nodes[i].prev = nodes[i - 1] if i < n - 1: nodes[i].next = nodes[i + 1] head = nodes[0] tail = nodes[n - 1] peaks = [] valleys = [] active_ids = {i for i in range(n)} for i in range(n - 1): if nodes[i].val > nodes[i + 1].val: heapq.heappush(peaks, (nodes[i].id, nodes[i])) elif nodes[i].val < nodes[i + 1].val: heapq.heappush(valleys, (nodes[i].id, nodes[i])) for turn in range(n - 1): to_remove = None if turn % 2 == 0: # Alex while peaks and peaks[0][0] not in active_ids: heapq.heappop(peaks) if peaks: to_remove = heapq.heappop(peaks)[1] else: to_remove = tail else: # Charlie while valleys and valleys[0][0] not in active_ids: heapq.heappop(valleys) if valleys: to_remove = heapq.heappop(valleys)[1] else: to_remove = tail active_ids.remove(to_remove.id) p, n_node = to_remove.prev, to_remove.next if p: p.next = n_node else: head = n_node if n_node: n_node.prev = p else: tail = p if p: if p.next: if p.val > p.next.val: heapq.heappush(peaks, (p.id, p)) elif p.val < p.next.val: heapq.heappush(valleys, (p.id, p)) return head.val ''' import sys s = sys.stdin.readline().strip() sol = solution() result = sol.finalCharacter(s) print(result) ''' ``` ```java import java.util.*; class Node { char val; int id; Node prev, next; Node(char val, int id) { this.val = val; this.id = id; } } class Solution { public static char finalCharacter(String S) { int n = S.length(); if (n <= 1) { return S.charAt(0); } Node[] nodes = new Node[n]; for (int i = 0; i < n; i++) { nodes[i] = new Node(S.charAt(i), i); } for (int i = 0; i < n; i++) { if (i > 0) nodes[i].prev = nodes[i - 1]; if (i < n - 1) nodes[i].next = nodes[i + 1]; } Node head = nodes[0]; Node tail = nodes[n - 1]; PriorityQueue peaks = new PriorityQueue<>(Comparator.comparingInt(a -> a.id)); PriorityQueue valleys = new PriorityQueue<>(Comparator.comparingInt(a -> a.id)); Set activeIds = new HashSet<>(); for (int i = 0; i < n; i++) { activeIds.add(i); } for (int i = 0; i < n - 1; i++) { if (nodes[i].val > nodes[i + 1].val) { peaks.add(nodes[i]); } else if (nodes[i].val < nodes[i + 1].val) { valleys.add(nodes[i]); } } for (int turn = 0; turn < n - 1; turn++) { Node toRemove = null; if (turn % 2 == 0) { // Alex while (!peaks.isEmpty() && !activeIds.contains(peaks.peek().id)) { peaks.poll(); } if (!peaks.isEmpty()) { toRemove = peaks.poll(); } else { toRemove = tail; } } else { // Charlie while (!valleys.isEmpty() && !activeIds.contains(valleys.peek().id)) { valleys.poll(); } if (!valleys.isEmpty()) { toRemove = valleys.poll(); } else { toRemove = tail; } } activeIds.remove(toRemove.id); Node p = toRemove.prev; Node nNode = toRemove.next; if (p != null) { p.next = nNode; } else { head = nNode; } if (nNode != null) { nNode.prev = p; } else { tail = p; } if (p != null) { if (p.next != null) { if (p.val > p.next.val) { peaks.add(p); } else if (p.val < p.next.val) { valleys.add(p); } } } } return head.val; } } /* public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.next(); char result = Solution.finalCharacter(s); System.out.println(result); } } */ ``` ```javascript class Node { constructor(val, id) { this.val = val; this.id = id; this.prev = null; this.next = null; } } // Basic Min-Priority Queue implementation for JS class PriorityQueue { constructor(comparator = (a, b) => a < b) { this._heap = []; this._comparator = comparator; } size() { return this._heap.length; } isEmpty() { return this.size() === 0; } peek() { return this._heap[0]; } push(value) { this._heap.push(value); this._siftUp(); } pop() { const poppedValue = this.peek(); const bottom = this.size() - 1; if (bottom > 0) { this._swap(0, bottom); } this._heap.pop(); this._siftDown(); return poppedValue; } _parent(i) { return ((i + 1) >>> 1) - 1; } _left(i) { return (i << 1) + 1; } _right(i) { return (i + 1) << 1; } _swap(i, j) { [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]; } _compare(i, j) { return this._comparator(this._heap[i], this._heap[j]); } _siftUp() { let node = this.size() - 1; while (node > 0 && this._compare(node, this._parent(node))) { this._swap(node, this._parent(node)); node = this._parent(node); } } _siftDown() { let node = 0; while ((this._left(node) < this.size() && this._compare(this._left(node), node)) || (this._right(node) < this.size() && this._compare(this._right(node), node))) { let maxChild = (this._right(node) < this.size() && this._compare(this._right(node), this._left(node))) ? this._right(node) : this._left(node); this._swap(node, maxChild); node = maxChild; } } } class Solution { static finalCharacter(S) { const n = S.length; if (n <= 1) return S[0]; const nodes = Array(n).fill(null).map((_, i) => new Node(S[i], i)); for (let i = 0; i < n; i++) { if (i > 0) nodes[i].prev = nodes[i - 1]; if (i < n - 1) nodes[i].next = nodes[i + 1]; } let head = nodes[0]; let tail = nodes[n - 1]; const comparator = (a, b) => a.id < b.id; const peaks = new PriorityQueue(comparator); const valleys = new PriorityQueue(comparator); const activeIds = new Set(); for (let i = 0; i < n; i++) activeIds.add(i); for (let i = 0; i < n - 1; i++) { if (nodes[i].val > nodes[i + 1].val) { peaks.push(nodes[i]); } else if (nodes[i].val < nodes[i + 1].val) { valleys.push(nodes[i]); } } for (let turn = 0; turn < n - 1; turn++) { let toRemove = null; if (turn % 2 === 0) { // Alex while (!peaks.isEmpty() && !activeIds.has(peaks.peek().id)) { peaks.pop(); } toRemove = !peaks.isEmpty() ? peaks.pop() : tail; } else { // Charlie while (!valleys.isEmpty() && !activeIds.has(valleys.peek().id)) { valleys.pop(); } toRemove = !valleys.isEmpty() ? valleys.pop() : tail; } activeIds.delete(toRemove.id); const p = toRemove.prev; const nNode = toRemove.next; if (p) p.next = nNode; else head = nNode; if (nNode) nNode.prev = p; else tail = p; if (p) { if (p.next) { if (p.val > p.next.val) peaks.push(p); else if (p.val < p.next.val) valleys.push(p); } } } return head.val; } } /* function main() { const fs = require("fs"); const s = fs.readFileSync(0, "utf8").trim(); const result = Solution.finalCharacter(s); console.log(result); } main(); */ ``` ### Complexity Analysis - **Time Complexity:** `O(N log N)` — Initialization takes `O(N log N)`, each turn does `O(log N)` operations, total `O(N log N)`. - **Space Complexity:** `O(N)` — Doubly linked list, priority queues, and set of active nodes.