字符串变换最小字符串_100分_B卷_字符串/分析模拟_始定一个字节串,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序

字符串变换最小字符串

题目描述：

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。
变换规则：交换字符串中任意两个不同位置的字符。

输入输出描述：

输入描述：

  一串小写字母组成的字符串s

输出描述：

  按照要求进行变换得到的最小字符串
  备注：
    s是都是小写字符组成
    1<=s.length<=1000

示例1：

输入：
	abcdef
输出：
	abcdef
说明：
	abcdef已经是最小字符串，不需要交换
1
2
3
4
5
6

示例2:

输入：
	bcdefa
输出：
	acdefb
说明：
	a和b进行位置交换，可以得到最小字符串
1
2
3
4
5
6

示例3:

输入：
	aaabbmncgch
输出：
	aaabbcncgmh
说明：
	a和b进行位置交换，可以得到最小字符串
1
2
3
4
5
6

解题思路：

题目的意思是只能交换两个字母，要让交换后的字符串是字典序最小的。
一读题目就容易想到暴力模拟，但是这题可以使用更简单的思路来求解：26个字母，如果a出现的话，那么a只有放在字符串第一个位置才能使得字符串的字典序最小；如果a、b出现的话，那么应该是所有a相继出现后，立马就是b出现，才会使得字符串字典序最小。——即：出现的所有的字母，应该按照ASCII码的大小出现，且相同的字母应该连续出现。所以解题思路为：
1、先统计出出现过的字母数量
2、按照统计结果，按照ASCII码值将出现过的字母连续摆放，如果摆放的时候，发现同置位的字母和原来的字符串中不相同，说明在原字符串的这个位置上出现了一个ASCII比较大的字母，应该交换这两个字母，这样会使得原来的字符串最小

代码：

public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	String line = scanner.nextLine();
	char[] chars = line.toCharArray();
	int[] count = new int[26];

	// 统计字符串中的字母数量
	for (char c : chars) {
		count[c - 'a']++;
	}

	int index = 0;
	for (int i = 0; i < 26; i++) {
		if (count[i] != 0) {
			// 前面的字母必须都是aaaa
			while (count[i] > 0 && line.charAt(index) == (char) (i + 'a')) {
				count[i]--;
				index++;
			}

			// 说明在原字符串中，前面出现的字母有比当前大的字母，交换
			if (count[i] > 0) {
				int j = chars.length - 1;
				while (j >= 0) {
					if (chars[j] == (char) (i + 'a')) {
						break;
					}
					j--;
				}

				char tmp = chars[j];
				chars[j] = chars[index];
				chars[index] = tmp;
				System.out.println(new String(chars));
				return;
			}
		}
	}

	// 原本就是最小的字符串了，不用交换
	if (index == chars.length) {
		System.out.println(line);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44