Description
给定一个包含 \(n\) 个小写字母的字符串 \(s\)。
现在,你可以将其中的最多一个字符移除(也可以不移除任何字符),你的目标是使这个字符串在字典序上尽可能小。
输出你可以得到的字典序上最小的字符串。
Input
第一行包含整数 \(T\),表示共有 \(T\) 组测试数据。
每组数据第一行包含整数 \(n\)。
第二行包含 \(n\) 个小写字母构成的字符串 \(s\)。
Output
每组数据输出一行结果,表示可得到的字典序最小的字符串。
Solution
简单题,可以发现需要得到最小的字符串,要求前面的字符尽可能小。
所以从前向后遍历字符串\(str\),如果发现一旦$str[i - 1] > str[i] \(,停止遍历,删掉\)str[i - 1]$,否则,删除最后一个字符(说明最后一个字符最大)
Code
#include <iostream>
using namespace std;
const int N = 200010;
char strs[N];
int main()
{
int T;
cin >> T;
while (T --)
{
int n;
cin >> n;
scanf("%s", strs);
int pos = -1;
for(int i = 1; i < n; i ++)
{
if(strs[i] < strs[i - 1])
{
pos = i - 1;
break;
}
}
if(pos == -1)
pos = n - 1;
for(int i = 0; i < n; i ++)
{
if(i != pos)
cout << strs[i];
}
cout << endl;
}
return 0;