LeetCode meituan-006. 小团的神秘暗号

Michael阿明

发布于 2021-09-06 03:40:27

25500

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录

- 1. 题目
- 2. 解题

1. 题目

小团深谙保密工作的重要性，因此在某些明文的传输中会使用一种加密策略，小团如果需要传输一个字符串 S ，则他会为这个字符串添加一个头部字符串和一个尾部字符串。

头部字符串满足至少包含一个 “MT” 子序列，且以 T 结尾。尾部字符串需要满足至少包含一个 “MT” 子序列，且以 M 开头。

例如 AAAMT 和 MAAAT 都是一个合法的头部字符串，而 MTAAA 就不是合法的头部字符串。很显然这样的头尾字符串并不一定是唯一的，因此我们还有一个约束，就是 S 是满足头尾字符串合法的情况下的最长的字符串。很显然这样的加密策略是支持解码的，给出一个加密后的字符串，请你找出中间被加密的字符串 S 。

格式：

输入：
- 输入第一行是一个正整数 n ，表示加密后的字符串总长度。
- 输入第二行是一个长度为 n 的仅由大写字母组成的字符串 T 。
输出：
- 输出仅包含一个字符串 S 。

示例：
输入：
     10
     MMATSATMMT
输出：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;
}