文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

小團深諳保密工作的重要性，因此在某些明文的傳輸中會使用一種加密策略，小團如果需要傳輸一個字符串 S ，則他會為這個字符串添加一個頭部字符串和一個尾部字符串。

頭部字符串滿足至少包含一個 “MT” 子序列，且以 T 結尾。
尾部字符串需要滿足至少包含一個 “MT” 子序列，且以 M 開頭。

例如 AAAMT 和 MAAAT 都是一個合法的頭部字符串，而 MTAAA 就不是合法的頭部字符串。
很顯然這樣的頭尾字符串并不一定是唯一的，因此我們還有一個約束，就是 S 是滿足頭尾字符串合法的情況下的最長的字符串。
很顯然這樣的加密策略是支持解碼的，給出一個加密后的字符串，請你找出中間被加密的字符串 S 。

格式：輸入： - 輸入第一行是一個正整數 n ，表示加密后的字符串總長度。 - 輸入第二行是一個長度為 n 的僅由大寫字母組成的字符串 T 。 輸出： - 輸出僅包含一個字符串 S 。示例： 輸入：10MMATSATMMT 輸出：SATM提示： 1 <= n <= 100000 請注意，本題需要自行編寫「標準輸入」和「標準輸出」邏輯， 以及自行 import/include 需要的 library

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/z3XKBp
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 貪心，找最短的前后綴，正向找到一次MT，反向找到一次TM

#include<bits/stdc++.h> using namespace std; int main() {int n;string s;cin >> n;cin >> s;bool m = false, t = false;int i = 0, j = s.size()-1;for( ; i < s.size(); ++i){if(s[i]=='M' && !m)m = true;else if(s[i]=='T' && m){i++;break;}}for( ; j >= 0; --j){if(s[j]=='T' && !t)t = true;else if(s[j]=='M' && t)break;}cout << s.substr(i, j-i);return 0; }

0 ms 3.6 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode meituan-006. 小团的神秘暗号的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。