# Leetcode 解題記錄 3563. Lexicographically Smallest String After Adjacent Removals
### 題目大意:
給定一個字串，相鄰的兩個字元如果字母的大小差一可以一起消掉(a和z相鄰也可以消)?求出最小字典序的結果。
example:
"rmlmlql" -> "l"
"fcddccec" -> "fcdcec"
### 解法思路:
這題一看到就會想能不能用stack做，但總是不對，很多例外，轉個方向考慮怎麼dp，狀態怎麼設計都不對，從前面跑從後面跑都怪怪的(花了一堆時間QQ)，因為前面的結果會因為字串變長之後影響到(類似stack的概念)，左思右想只好試看看graph的方法，建圖的方式也很簡單，就是將可以消成空字元的片段記錄起來，假設"rmlmlql" (0-index)
link[0][5] = 1
link[1][2] = 1
link[1][4] = 1
link[2][3] = 1
...
過程要處理的就是link[i][j] = link[i][k]&link[k+1][j] ，有一個k成立就是可消的。另外就是s[i]和s[j]可消，且link[i+1][j-1]是true也可消。

利用這個link，從頭bfs到尾，就可以解了，複雜度為O(N^3)。
[code](https://github.com/zBING-QIAN/CodingPractice/blob/main/Leetcode_Record/P_3563.cpp)
### Murmur
這題在沒法在時間內寫完(其實是想到了隔天才解的...)，但看了一下AI的表現也可以看出來這題(Q4)是有點難度的，字串處理的題目比較少會想到用graph來解，前面想說搞stack dp就能解的我還是too naive了。

(上個禮拜少數值得開心的事🐟SABA)