ZeroJudge 解題筆記：s216.三仙鬥法 (Competition)

作者：王一哲
日期：2026年9月2日


ZeroJudge 題目連結：s216.三仙鬥法 (Competition)

題目 pdf 檔連結：三仙鬥法 (Competition)

解題想法

題目是多筆測資。每筆測資第一列是一個整數 $R$，代表共有 $R$ 輪比賽；第二列有 3 個正整數 $a, b, c ~(1 \leq a, b, c \leq 10^{18})$，代表 3 個學院派出的選手靈氣值。每回合行動時，靈氣值最低的選手恢復 1 點靈氣值，較高的 2 個選手各減 1 點靈氣值；如果有多個選手的靈氣值最低，每個選手皆有相同的機率恢復 1 點靈氣值；不斷執行直到同時有 2 個選手的靈氣值歸零，此時靈氣值還沒有歸零的選手獲勝。題目要回傳每回合獲勝選手代表的學院，A、B、C 其中一個字母；如果三個學院獲勝機率相等，回傳 A B C。

由於這題的靈氣值很大，如果真的模擬比賽過程一定會超時，要找數學規律解題。由於 3 個選手其中 2 個的靈氣值減 1，另 1 個選手靈氣值加 1，所有選手的靈氣值都會加 1 或減 1。如果其中 2 個選手的靈氣值為來是偶數、另 1 個選手的靈氣值原為奇數，經過 1 個回合之後 2 個人的靈氣值同時變為奇數、另 1 個人的靈氣值變為偶數，因此只有這 2 個人的靈氣值同時歸零才會結束這輪比賽，一定是另 1 個選手獲勝。如果 3 個選手的靈氣值皆為偶數或奇數，經過多個回合之後 3 個人的靈氣值會相等，獲勝機率相同，答案是 A B C。因此這題不需要模擬比賽過程，只要用 $a, b, c$ 的奇偶性就可以直接輸出答案。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 11.4 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for token in line.split():
                yield int(token)
    
    tokens = get_tokens()
    result = []
    while True:
        try:
            R = next(tokens)
        except StopIteration:
            break
        
        for _ in range(R):
            a = next(tokens) % 2
            b = next(tokens) % 2
            c = next(tokens) % 2
            if a == b == c:
                result.append("A B C\n")
            elif b == c:
                result.append("A\n")
            elif a == c:
                result.append("B\n")
            elif a == b:
                result.append("C\n")
        
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3875. Construct Uniform Parity Array I

作者：王一哲
日期：2026年9月2日


LeetCode 題目連結：3875. Construct Uniform Parity Array I

解題想法

簡單題，直接回傳 True。如果 $nums1$ 的數字皆為奇數或偶數，直接複製 $nums1$ 到 $nums2$ 就能符合條件。如果 $nums1$ 的數字同時有奇數及偶數，一定能將 $nums2$ 全部湊成奇數，有兩種狀況：

1. $nums1[i]$ 是奇數，直接複製到 $nums2[i]$。
2. $nums1[i]$ 是偶數，一定能找到一個是奇數的 $nums1[j]$，將 $nums1[i] - nums1[j]$ 複製到 $nums2[i]$。

結論：題目的要求一定成立。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.23 MB, beats 47.47%.

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        return True

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 30.46 MB, beats 7.23%.

class Solution {
public:
    bool uniformArray(vector<int>& nums1) {
        return true;
    }
};

ZeroJudge 解題筆記：s215.紙膠帶 (Tape)

作者：王一哲
日期：2026年9月1日


ZeroJudge 題目連結：s215.紙膠帶 (Tape)

題目 pdf 檔連結：紙膠帶 (Tape)

解題想法

題目是多筆測資。每筆測資第一列是代表紙膠帶長度的整數 $N$，第二列有 26 個正整數代表每種動物（字母）數量上限，第三列是代表紙膠帶圖案的字串。題目規定一段連續的漂亮紙帶必須符合以下 2 個條件：

1. 紙帶上正好有 3 種動物
2. 紙帶上最多只能有 1 種動物數量超過上限

這題要找符合條件的連續子字串，很適合用滑動視窗 (sliding window) 解題。不過麻煩的地方在於計分方式有 2 種：

1. 紙帶上沒有動物超過數量上限，以 3 種動物的最大數量計分。
2. 紙帶上正好有 1 種物物超過數量上限，以超過上限的數量計分。

為了保證滑動視窗取對範圍，要分別對 2 種計分方式各跑一次滑動視窗，因為可能在一段較短的視窗內正好有 1 種物物超過數量上限，但是這個數量很大，分數反而可能很高。

Python 程式碼

使用時間約為 0.8 s，記憶體約為 10.9 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for token in line.split():
                yield token
        
    tokens = get_tokens()
    
    result = []
    while True:
        try:
            N = int(next(tokens))
            limits = [0] * 26
            for i in range(26):
                limits[i] = int(next(tokens))
            s = next(tokens)
        except StopIteration:
            break
        
        def get_score(max_exceed):
            # 自訂函式，用滑動視窗取連續子字串分數，代入可以有幾個字母超標
            left = 0  # 視窗左端點
            imax = 0  # 最高分數
            curr = set()  # 視窗中的字母索引值
            exceed = set()  # 超標的字母
            cnt = [0] * 26  # 視窗中的字母計數器
            for right in range(N):  # 右端點 0 ~ N-1
                ri_idx = ord(s[right]) - ord('a')  # 右端點字母索引值
                curr.add(ri_idx)  # ri_idx 加入 curr
                cnt[ri_idx] += 1  # ri_idx 數量加 1
                # 如果 ri_idx 超標，ri_idx 加入 exceed
                if cnt[ri_idx] == limits[ri_idx] + 1: exceed.add(ri_idx)
                # 左端點向右滑，直到視窗內字母種類等於 3 且超標數量等於 max_exceed
                while left < right and (len(curr) > 3 or len(exceed) > max_exceed):
                    le_idx = ord(s[left]) - ord('a')  # 左端點字母索引值
                    left += 1
                    cnt[le_idx] -= 1
                    # 如果 le_idx 降回數量上限，exceed 移除 le_idx
                    if cnt[le_idx] == limits[le_idx]: exceed.remove(le_idx)
                    # 如果 le_idx 降回數量歸零，curr 移除 le_idx
                    if cnt[le_idx] == 0: curr.remove(le_idx)
                
                # 依照 max_exceed 計分
                score = 0
                if len(curr) == 3:  # 有 3 種字母才有分數
                    if max_exceed == 1 and len(exceed) == 1:  # 只有一種超標，這個字母數量是分數
                        score = cnt[list(exceed)[0]]
                    elif max_exceed == 0 and len(exceed) == 0:  # 沒有字母超標，curr 之中 3 個字母數量最大值是分數
                        score = max(cnt[idx] for idx in curr)
                # 更新最高分數
                imax = max(imax, score)
            return imax
        # 用兩次滑動視窗找最高分
        ans = max(get_score(0), get_score(1))
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3568. Minimum Moves to Clean the Classroom

作者：王一哲
日期：2026年9月1日


LeetCode 題目連結：3568. Minimum Moves to Clean the Classroom

解題想法

中等難度題。題目給一個長度為 $m$ 的陣列 $classroom$，其中包含 $m$ 個長度為 $n$ 的字串，字串中只包含以下的字元：

• S 代表這格是學生的初位置
• L 代表這格有垃圾
• R 代表可以恢復能量的格子
• X 代表這格有障礙物，學生不能走到這格。
• . 代表空格

另外給一個整數 $energy$ 代表學生一開始的能量。假設學生每走一格消耗 1 點能量，如果能量歸零時不是位在 R 的格子上，學生無法再移動。如果學生走到 L 的格子上，可以撿起垃圾。如果學生走到 R 的格子上，會將能量補到起始值 $energy$。題目要問學生撿起所有垃圾時需要移動的最少步數，如果無法撿起所有的垃圾則回傳 $-1$。

這題的下方有提示，要用 BFS 解題，待走訪佇列放入的資料為 (x 座標, y 座標, 已撿起的垃圾狀態 mask, 目前的能量 e, 已走的步數 step)，並用一個三維陣列 bestEnergy 代表走到座標 (x, y) 時、狀態為 mask 的最高能量，並用 bestEnergy 剪枝。由於這題的垃圾數量上限為 10 個，可以先將每個位置的垃圾編號，用二進位制記錄這個編號的垃圾是否已被撿起來。詳細的 BFS 過程請參考程式碼中的註解。

Python 程式碼

Runtime: 1511 ms, beats 91.23%. Memory: 24.54 MB, beats 94.74%.

class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int:
        m, n = len(classroom), len(classroom[0])  # 教室尺寸 m*n
        # 1. 先找到起點 S 的位置、垃圾 L 的位置
        xi, yi = 0, 0  # S 的位置
        litter_pos = dict()  # 特定位置垃圾對應的編號
        litter_idx = 0   # 垃圾的編號
        for i in range(m):
            for j in range(n):
                ch = classroom[i][j]
                if ch == 'S':
                    xi, yi = i, j
                elif ch == 'L':
                    litter_pos[i, j] = litter_idx
                    litter_idx += 1
        
        total_litters = litter_idx  # 垃圾數量
        fullMask = (1 << total_litters) - 1  # 拿到所有垃圾的狀態
        
        # 特例，如果沒有垃圾，回傳 0
        if total_litters == 0: return 0
        
        # 2. BFS，待走訪佇列放入 (x 座標, y 座標, 狀態, 能量, 步數)
        que = deque([(xi, yi, 0, energy, 0)])
        # bestEnergy[x][y][mask] 代表走到 x, y, mask 狀態時最高的能量，預設為 -1
        bestEnergy = [[[-1] * (1 << total_litters) for _ in range(n)] for _ in range(m)]
        bestEnergy[xi][yi][0] = energy  # 起始狀態能量全滿
        # BFS
        while que:
            x, y, mask, e, step = que.popleft()
            # 如果 能量 e 為 0 且不在 R 上面，無法再移動
            if e == 0 and classroom[x][y] != 'R':
                continue
            # 四方位檢查
            for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nx, ny = x + dx, y + dy
                # 如果沒有出界也沒有遇到障礙物 X
                if 0 <= nx < m and 0 <= ny < n and classroom[nx][ny] != 'X':
                    ne = e - 1  # 能量減 1
                    if ne < 0: continue  # 能量不足
                    nxt_mask = mask  # 新的狀態
                    if classroom[nx][ny] == 'L':  # 撿垃圾
                        nxt_mask |= (1 << litter_pos[nx, ny])  # 更新狀態
                    elif classroom[nx][ny] == 'R':  # 能量全滿
                        ne = energy
                    
                    # 如果 nxt_mask == fullMask，找到答案，回傳 step + 1
                    if nxt_mask == fullMask: return step + 1
                    
                    # 如果 ne 大於之前走到 [nx][ny][mask] 的能量，才將下一步加入 que
                    if ne > bestEnergy[nx][ny][nxt_mask]:
                        bestEnergy[nx][ny][nxt_mask] = ne
                        que.append((nx, ny, nxt_mask, ne, step + 1))
        # 如果走完 BFS 還沒有找到 fullMask，無法達成目標，回傳 -1
        return -1

LeetCode 解題筆記：2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

作者：王一哲
日期：2026年8月31日


LeetCode 題目連結：2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

解題想法

中等難度題。題目一個鏈結串列的開頭節點 $head$，如果鏈結串列之中某個節點的值同時大於前、後節點的值，或是同時小於前、後節點的值，這樣的節點稱為關鍵點 (critical point)，鏈結串列頭、尾的節點不會是關鍵點。題目要回傳兩個關鍵點的最小與最大距離，如果只有1個或沒有關鍵點，無法取距離，回傳 $[-1, -1]$。

可以先建立一個節點 $pre$ 指向 $head$，另一個走訪用的虛擬節點 $dummy$ 指向 $head.next$，再用一個 while 迴圈走訪所有的節點，如果還有 $dummy.next$ 繼續執行。再建一個陣列 $pos$ 儲存關鍵點的位置，用變數 $imin$ 儲存最小的距離，$step$ 儲存目前的節點與 $head$ 的距離。每次執行 while 迴圈時，先檢查這個節點的值是否同時大於 $pre$ 或 $dummy.next$ 的值，或是同時小於 $pre$ 或 $dummy.next$ 的值，如果 $pos$ 已經有資料，檢查 $step - pos[-1]$ 是否是新的最小值，再將 $step$ 加入 $pos$。如果最後 $pos$ 長度小於 2，回傳 $[-1, -1]$；反之，回傳 $[imin, pos[-1] - pos[0]]$。

Python 程式碼

Runtime: 65 ms, beats 90.43%. Memory: 63.25 MB, beats 23.68%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        pre = head  # 前一個節點，先指向 head
        dummy = head.next  # 走訪用的虛擬節點，先指向 head.next
        step = 0  # 目前節點與 head 的距離
        pos = []  # 關鍵節點與 head 的距離
        imin = float('inf')  # 最矩距離
        while dummy.next:  # 如果有 dummy.next 繼續執行
            step += 1
            # 檢查 dummy 是否同時比前、後節點小或同時比前、後節點大
            if (pre.val > dummy.val and dummy.next.val > dummy.val) or (pre.val < dummy.val and dummy.next.val < dummy.val):
                if pos: imin = min(imin, step - pos[-1])  # 如果 pos 已經有資料，更新 imin
                pos.append(step)  # 加入 step
            pre = dummy  # pre 指向現在的 dummy
            dummy = dummy.next  # dummy 指向下一格
        
        # 如果關鍵節點不到 2 個，無法取距離，回傳 [-1, -1]
        if len(pos) < 2:
            return [-1, -1]
        else:  # 可以找距離，最遠距離為 pos 兩端
            return [imin, pos[-1] - pos[0]]

LeetCode 解題筆記：2091. Removing Minimum and Maximum From Array

作者：王一哲
日期：2026年8月30日


LeetCode 題目連結：2091. Removing Minimum and Maximum From Array

解題想法

中等難度題。題目給一個陣列 $nums$，要刪除 $nums$ 之中的最大值及最小值，可以從陣列兩端往中間刪除數字，回傳最少的刪除數量。解題時先找出最大值、最小值的索引值，取兩者的最小值為 $left$、最大值為 $right$，$nums$ 長度為 $n$，接下來只有 3 種可能性：

1. 從陣列開頭往後刪除，刪除索引值 $0$ 到 $right$，數量為 $right + 1$。
2. 從陣列結尾往後前除，刪除索引值 $n-1$ 到 $left$，數量為 $n - left$。
3. 從陣列兩端同時往中間刪除，刪除索引值 $0$ 到 $left$ 及 $n-1$ 到 $right$，數量為 $left + 1 + n - right$。

答案是以上 3 種數量的最小值。

Python 程式碼

Runtime: 12 ms, beats 88.52%. Memory: 33.64 MB, beats 35.35%.

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        n = len(nums)  # 長度
        max_pos = nums.index(max(nums))  # 最大值的索引值
        min_pos = nums.index(min(nums))  # 最小值的索引值
        left = min(max_pos, min_pos)  # 左側目標索引值
        right = max(max_pos, min_pos)  # 右側目標索引值
        return min(right + 1, n - left, left + 1 + n - right)

ZeroJudge 解題筆記：s214.細菌繁殖 (Bacteria)

作者：王一哲
日期：2026年8月30日


ZeroJudge 題目連結：s214.細菌繁殖 (Bacteria)
題目 pdf 檔連結：細菌繁殖 (Bacteria)

解題想法

題目為多筆測資。測資開頭為 $M, N, K, T$ 四個整數，分別代表地圖為 $M$ 列、$N$ 欄；共有 $K$ 種細菌，編號為 $1$ ~ $K$；回傳經過時間 $T$ 之後各種類細菌數量。接下來有 $M$ 列、每列 $N$ 個整數，數字 0 代表目前沒有細菌的格子，$-1$ 代表無法走到的格子，正整數代表這格的細菌編號。如果同時有多種細菌走到同一格，由編號較小的細菌佔領此格。測資範圍為 $K \leq M \times N \leq 2 \times 10^5$，$T < 2 \times 10^9$。

這題考 BFS，從一開始有細菌的格子出發，每次檢查上、下、左、右的格子是否為 0，直到沒有格子可以佔領或是時間到為止。為了配合「如果同時有多種細菌走到同一格，由編號較小的細菌佔領此格」的規則，先掃過一開始的地圖 $grid$，將有細菌的格子座標依照細菌編號填入長度為 $K+1$ 的二維陣列 $sources$ 之中；接下來將 $sources$ 的資料，依照細菌編號由小到大放入待走訪佇列 $que$ 之中，這樣在用 BFS 向外傳播時，編號小的細菌會先抵達格子，直接修改 $grid$ 此格的編號，如果之後有編號較大的細菌也走到這格時就無法佔領。

這題還有一些陷阱，例如時間 $T$ 最大約為 $2 \times 10^9$，可能在時間還沒到之前地圖上就沒有格子能走了，如果直接用一個 for 迴圈跑 $T$ 次可能會超時。解決方法是用另一個二維陣列 $time$ 儲存格子第一次有細菌抵達的時間，當 BFS 走到某個格子的時間已經等於 $T$ 就可以中止迴圈，或是 $que$ 已經是空的也可以中止迴圈。

另一個陷阱是 Python 才會遇到的記憶體限制 64 MB，如果用 sys.stdin.read().split() 一次讀取所有測資並分割，會超出記憶體上限，要改用生成器，每次轉換一個數字。而且直接用二維串列儲存 $grid, time$ 資料，運算速度會比較慢而且使用較多的記憶體，改用 array 函式庫的 array 並將二維陣列攤平成一維，才樣才能過關。

Python 程式碼

記憶體爆掉，通過 85% 的測資。

def solve():
    import sys
    from collections import deque
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取測資，地圖 grid，有細菌的格子 source，計數器 cnt
        M = int(data[ptr])
        N = int(data[ptr + 1])
        K = int(data[ptr + 2])
        T = int(data[ptr + 3])
        ptr += 4
        grid = []
        for _ in range(M):
            row = list(map(int, data[ptr : ptr + N]))
            ptr += N
            grid.append(row)
        
        sources = [[] for _ in range(K + 1)]
        cnt = [0] * (K + 1)
        for i in range(M):
            for j in range(N):
                d = grid[i][j]
                if d > 0:
                     sources[d].append((i, j))
                     cnt[d] += 1
        
        # 從 sources 取出位置加入待走訪序列 que
        que = deque()
        for source in sources:
            for pos in source:
                que.append(pos)
        
        # 執行時間等於 T 或是直到 que 為空
        time = [[0] * N for _ in range(M)]  # 首次有細菌抵達的時
        dr = (0, 1, 0, -1)
        dc =(1, 0, -1, 0)
        while que and time[que[0][0]][que[0][1]] < T:
            r, c = que.popleft()
            d = grid[r][c]
            t = time[r][c]
            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]
                if 0 <= nr < M and 0 <= nc < N and grid[nr][nc] == 0:
                    grid[nr][nc] = d
                    time[nr][nc] = t + 1
                    cnt[d] += 1
                    que.append((nr, nc))
        
        res = " ".join(map(str, cnt[1:])) + "\n"
        result.append(res)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：2948. Make Lexicographically Smallest Array by Swapping Elements

作者：王一哲
日期：2026年8月29日


LeetCode 題目連結：2948. Make Lexicographically Smallest Array by Swapping Elements

解題想法

中等難度題。題目給一個陣列 $nums$ 及整數 $limit$，每次操作時可以選擇陣列中的兩個整數 $nums[i], nums[j]$，如果 $| nums[i] - nums[j] | \leq limit$ 可以將兩者的位置交換，操作次數不限，回傳可得的最小字典序陣列。這題我是將 $nums$ 之中的數值及索引值組成 tuple 或 pair 存入另一個陣列 $data$ 之中，將 $data$ 依照數值由小到大排序；依序由排序後的 $data$ 讀取資料，將數值及索引值分組分別存入陣列 $values$ 及 $indices$；再從 $values$ 及 $indices$ 讀取分組後的數值，將同組的索引值排序之後，依照索引值將數值填入 $nums$ 之中。

Python 程式碼

Runtime: 259 ms, beats 68.66%. Memory: 54.76 MB, beats 43.28%.

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        # 將 nums 之中的值組成 (num, idx) 放入 data 之中再排序
        data = sorted((num, idx) for idx, num in enumerate(nums))
        # 相差 k 以內的數字放同一組，數字、索引值分開放
        values = [[data[0][0]]]
        indices = [[data[0][1]]]
        for val, idx in data[1:]:
            if val - values[-1][-1] <= limit:  # 可以放在最後一組
                values[-1].append(val)
                indices[-1].append(idx)
            else:  # 新的一組
                values.append([val])
                indices.append([idx])
        # indices 每組排序後，依照 idx 將 values 的值填入 nums 再回傳
        for vals, idxs in zip(values, indices):
            idxs.sort()
            for val, idx in zip(vals, idxs):
                nums[idx] = val
        return nums

ZeroJudge 解題筆記：n129.p1. 鋪磁磚問題

作者：王一哲
日期：2026年8月28日


ZeroJudge 題目連結：n129.p1. 鋪磁磚問題

解題想法

題目只給一個整數 $n$，代表地板的總面積為 $1 \times n$，有 3 種可以用的地板面積 $1 \times 1$、$1 \times 2$、$1 \times 3$，要回傳組成長度 $n$ 的所有方法數。這題考無限背包，開一個長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表地板總長度為 $i$ 的方法數。但是題目要找的是排列方法數，外層 for 迴圈要跑地板總長度 $1$ 到 $n$，內層的 for 迴圈跑可以用的地板長度 $1、2、3$，最後答案在 $dp[n]$。

Python 程式碼

使用時間約為 13 ms，記憶體約為 9.6 MB，通過測試。

n = int(input())  # 地板 1*n
dp = [0] * (n+1)  # 組成地板長度 i 的方法數
dp[0] = 1  # 長度 0 方法數 1
for j in range(1, n+1):  # 這題是排列，要先跑長度
    for p in range(1, 4):  # 三種地板長度 1, 2, 3
        if j >= p: dp[j] += dp[j - p]
print(dp[n])

C++ 程式碼

使用時間約為 1 ms，記憶體約為 3.9 MB，通過測試。

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // 地板 1*n
    vector<long long> dp (n+1, 0);  // 組成地板長度 i 的方法數
    dp[0] = 1;  // 長度 0 方法數 1
    for(int j = 1; j <= n; j++) {  // 這題是排列，要先跑長度
        for(int p = 1; p <= 3; p++) {  // 三種地板長度 1, 2, 3
            if (j >= p) dp[j] += dp[j - p];
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}

LeetCode 解題筆記：3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

作者：王一哲
日期：2026年8月28日


LeetCode 題目連結：3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

解題想法

困難題。題目給一個原來的字串 $s$ 及目標字串 $target$，兩個字串長度皆為 $n$，要找到一個大於 $target$ 且字典序最小的迴文字串，如果沒有則回傳空字串。這題與昨天的題目 3720. Lexicographically Smallest Permutation Greater Than Target 很像，但是多了迴文的條件，難度高很多。主要分成以下 3 個步驟：

1. 先檢查 $s$ 是否能組成迴文字串
2. 準備前半段可用的字母並將相異字母排序
3. 用 DFS 遞迴及回溯找答案，但是要加上剪枝節省時間，剪枝條件有
   1. 如果 is_greater 等於 False，不能放比 $target[idx]$ 小的字母。
   2. 如果 new_is_greater 等於 True，用剩下的字母組成答案。

Python 程式碼

Runtime: 11 ms, beats 90.91%. Memory: 20.40 MB, beats 7.58%.

class Solution:
    def lexPalindromicPermutation(self, s: str, target: str) -> str:
        n = len(s)  # 長度
        cnt = Counter(s)  # 字母計數器

        # 1. 先檢查 s 是否能組成迴文字串
        odd_cnt = 0  # 有幾個字母的數量為奇數數量
        mid_char = ""  # 如果某個字母數量為奇數，只能放在中間
        for char, freq in cnt.items():
            if freq % 2 == 1:
                odd_cnt += 1
                mid_char = char
        if odd_cnt > 1:  # 不只一個字母數量是奇數，回傳空字串
            return ""

        # 2. 準備前半段可用的字母並將相異字母排序
        half_cnt = {char: freq // 2 for char, freq in cnt.items() if freq // 2 > 0}
        unique_chars = sorted(half_cnt.keys())
        ans = ""  # 答案
        m = n // 2  # 前半段長度

        # 3. 主要的解題過程
        def dfs(idx, is_greater, path):
            nonlocal ans
            if ans: return True

            # 遞迴出口，已經填滿前半段
            if idx == m:
                # 組合成整個字串 = 前半段 + 中間字母 + path 反序組成的後半段
                full = "".join(path) + mid_char + "".join(path[::-1])
                # 如果 full > target，找到答案
                if full > target:
                    ans = full
                    return True
                return False

            # 由小到大檢查可用的字母
            for char in unique_chars:
                # 跳過已經用完的字母
                if half_cnt[char] == 0: continue
                # 剪枝，如果 is_greater == False，不能放比 target[idx] 小的字母
                if not is_greater and char < target[idx]: continue
                # 更新 char 的數量、path 及狀態
                half_cnt[char] -= 1
                path.append(char)
                new_is_greater = is_greater or (char > target[idx])
                # 剪枝，如果 new_is_greater == True，用剩下的字母組成答案
                if new_is_greater:
                    # 找出剩下的字母
                    rem = []
                    for c in unique_chars:
                        rem.extend([c] * half_cnt[c])
                    # 組成完整的前半段字串
                    first = "".join(path) + "".join(rem)
                    # 組成完整的答案
                    ans = first + mid_char + first[::-1]
                    return True
                # 遞迴
                if dfs(idx + 1, new_is_greater, path): return True
                # 回溯
                path.pop()
                half_cnt[char] += 1
            # 預設回傳 False
            return False

        # 呼叫 dfs 找答案
        dfs(0, False, [])
        return ans