767. 重构字符串

问题767 重构字符串 ★★☆☆☆

https://leetcode.cn/problems/reorganize-string/

刚入手这个题目时，有点想当然了，直觉上的思路是先计数字符个数，然后按个数由大到小，往重组后的字符串里塞，当找不到可塞的位置时，认为是bad case. 提交以后不通过，很快就发现了问题在哪。一个简单的例子，假设个数最少的字符是两个，其他字符都很好的塞到了重组后字符串的最左端，现在还剩下两个位置，那么就会处理成bad case, 但其实这并不是bad case. 所以，该怎么解决这个问题呢？其实这个时候，我们只需要把上一轮的字符往后塞就可以了。OK，当前轮处理发现进行不下去了，需要回到上一轮重新调整，这不就是回溯么？所以，如果一开始就从回溯的角度考虑，思路就很容易打开了，甚至不需要计数字符个数，就是遍历原字符串，挨个往重组后的字符串里塞，塞不下去了就往前回溯，处理到原字符串末尾时说明已经得到了一个符合条件的重组字符串。按照这个思路写了一版之后提交，发现还是没通过，超时了……。看了一下超时case，应该是bad case导致的递归深度太大。在最外层加了一个可行性判断，回溯时也优化了下，改为每次取剩余计数最多的字符优先处理。提交通过，只是效率还是一般。

看了一下官方题解，官方题解里通过堆来维护字符个数，然后每次取个数top2的两个字符往结果字符串里塞这个处理方法还是有一定启发性的，尤其是每次取个数top2的两个字符，稍微思考下就能明白确实是简洁有效的处理方法，可以理解成贪婪算法。

参考官方题解，把回溯法的版本又改了一下，确实没有必要按回溯处理。不过我没有使用堆，从计数数组里也很容易计算出当前个数top2的字符。

	public String reorganizeString(String s) {
		char[] origin = s.toCharArray();

		int maxCount = 0, allCount = origin.length;

		int[] count = new int[26];
		for (int i = 0; i < origin.length; i++) {
			int idx = origin[i] - 'a';
			count[idx]++;

			if (count[idx] > maxCount) {
				maxCount = count[idx];
			}
		}

		if (allCount - maxCount < maxCount - 1) {
			return "";
		}

		StringBuilder builder = new StringBuilder();

		int maxCountIdx, secondMaxCountIdx;
		while (true) {
			int[] top2CountCharsIdx = getTop2CountCharsIdx(count);

			maxCountIdx = top2CountCharsIdx[0];
			secondMaxCountIdx = top2CountCharsIdx[1];
			if (maxCountIdx == -1 && secondMaxCountIdx == -1) {
				break;
			}

			if (maxCountIdx != -1) {
				builder.append((char)('a' + maxCountIdx));
				count[maxCountIdx]--;
			}
			if (secondMaxCountIdx != -1) {
				builder.append((char)('a' + secondMaxCountIdx));
				count[secondMaxCountIdx]--;
			}
		}

		return builder.toString();
	}

	private int[] getTop2CountCharsIdx(int[] count) {
		int maxCount = 0, maxCountIdx = -1, secondMaxCount = 0, secondMaxCountIdx = -1;
		for (int i = 0; i < count.length; i++) {
			if (count[i] > maxCount) {
				secondMaxCount = maxCount;
				secondMaxCountIdx = maxCountIdx;

				maxCount = count[i];
				maxCountIdx = i;
			} else if (count[i] > secondMaxCount) {
				secondMaxCount = count[i];
				secondMaxCountIdx = i;
			}
		}

		return new int[] {maxCountIdx, secondMaxCountIdx};
	}

在 LeetCode 查看