作者 : Xia Xinyu
日期 : 2021-08-16
原题链接
题目 :给定一个包含 n 个小写字母的字符串 s。
现在,你可以将其中的最多一个字符移除(也可以不移除任何字符),你的目标是使这个字符串在字典序上尽可能小。
输出你可以得到的字典序上最小的字符串。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 n。
第二行包含 n 个小写字母构成的字符串 s。
输出格式
每组数据输出一行结果,表示可得到的字典序最小的字符串。
数据范围
1≤T≤10,
2≤n≤2×105,
同一测试点内,所有 n 的和不超过 2×105。
输入样例:
2
3
aaa
5
abcda
输出样例:
aa
abca
思路:判断字符串是不是非递减的字符串,如果是,则输出前n - 1个字符即可,否则去掉第一个比后一个字符大的字符。
代码:
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while(T-- != 0){
int n = in.nextInt();
String s = in.next();
var a = s.toCharArray();
int i;
var flag = new boolean[n];
for(i = 0;i < n - 1;i++){
if(a[i + 1] < a[i]){
flag[i] = true;
break;
}
}
if(i == (n - 1)) n--;
for(i = 0;i < n;i++)
{
if(flag[i]) continue;
System.out.print(a[i]);
}
System.out.println();
}
}
}