【美团3.18校招真题2】

大厂笔试真题网址：https://codefun2000.com/

塔子哥刷题网站博客：https://blog.codefun2000.com/

最多修改两个字符，生成字典序最小的回文串

提交网址：https://codefun2000.com/p/P1089

由于字符串经过修改一定为回文串，且最多修改两次，所以原字符串位置i与对称位置n-i-1不一样的个数最多为2。所以统计一下需要改的位置个数，记为cnt

1. cnt=0，即原字符串就是回文串，找到第一个不为a的位置i，将i与对称位置n-i-1都改为a

aca      ---> aaa
acca     ---> aaaa
acbca    ---> aabaa 
1
2
3

2. cnt=1，只有一个位置需要修改，此时分两种情况
   • 如果 i与对称位置n-i-1都不是a，将这俩位置都改为a即可
   • 如果 i与对称位置n-i-1只有一个为a，将另一个不是a的改为a。此时只改了一个字母，还可以改一个。当字符串长度为奇数时，将中间字符改为a

abcdba  ---> abaaba
abcea   ---> aacaa
cbcac   ---> caaac  
1
2
3

3. cnt=2，两个对称位置需要修改， i与对称位置n-i-1，谁小就改为谁

abcde  ---> abcba
1

int main() {
	string s;
	cin >> s;
	int n = s.size();
	vector<int> idxs;
	for (int i = 0; i < n / 2; i++) {
		if (s[i] != s[n - 1 - i]) {
			idxs.push_back(i);
		}
	}
	int cnt = idxs.size();
	if (cnt == 0) {
		// 本身就是回文串，需要找到第一个不是a的地方修改
		for (int i = 0; i <= n / 2; i++) {
			if (s[i] != 'a') {
				s[i] = 'a';
				s[n - 1 - i] = 'a';
				break;
			}
		}
	}
	else if (cnt == 1) {
		// 只有一个需要修改的地方
		if (s[idxs[0]] != 'a' && s[n - 1 - idxs[0]] != 'a') {
			// 如果对称位置都不是a，则两个都改为a
			s[idxs[0]] = 'a';
			s[n - 1 - idxs[0]] = 'a';
		}
		else {
			// 如果只有一个为a，则修改不是a的那个
			// 如果当前串为奇数，还要修改中间位置的为a
			s[idxs[0]] = 'a';
			s[n - 1 - idxs[0]] = 'a';
			if (n & 1) {
				s[n / 2] = 'a';
			}
		}
	}
	else {
		// 有两个需要修改的地方，当前位置idxs[i]和对称位置n - 1 - idxs[i]，谁小就改为谁
		for (int i = 0; i < cnt; i++) {
			char c = min(s[idxs[i]], s[n - 1 - idxs[i]]);
			s[idxs[i]] = c;
			s[n - 1 - idxs[i]] = c;
		}
	}
	cout << s << endl;
	return 0;
}
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
45
46
47
48
49