题目
字符串S由小写字母构成,长度为n。定义一种操作,每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后,字符串中最多有多少个连续的位置上的字母相同?链接
思路
- 记录每个字母出现的下标。对每一个字母出现的所有位置,进行滑窗计算移动代价。
- 窗口从一个元素开始扩大,计算代价超过要求,缩小窗口,否则扩大窗口。
- 由经验可得,要把滑窗内所有位置移动到连续位置,两边元素靠中间元素移动的代价较小。
比如字母a
的所有下标情况为[11,13,15,17,19|21,23,25,30,31]
,选取中间靠左的(19
, 选中间的任意都行)需要分别计算左右移动到中间元素的代价是多少.
左边移动为[15,16,17,18,19]
计算得到代价10
,右边移动为[19,20,21,22,23,24]
代价为21
。
判断代价是否超过要求。不超过要求更新结果。
循环所有的字母情况。
import java.util.*;
public class Main {
static Map<Character, List<Integer>> map = new HashMap<>();
static Map<Character, List<Integer>> mapPreSum = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String[] split = s.split(" ");
String str = split[0];
int m = Integer.parseInt(split[1]);
for (int i = 0; i < str.length(); i++) {
List<Integer> idxes = map.getOrDefault(str.charAt(i), new ArrayList<>());
List<Integer> preSum = mapPreSum.getOrDefault(str.charAt(i), new ArrayList<>());
idxes.add(i);
preSum.add(preSum.size() == 0 ? i : preSum.get(preSum.size() - 1) + i);
map.put(str.charAt(i), idxes);
mapPreSum.put(str.charAt(i), preSum);
}
int res = 0;
for (Character c : map.keySet()) {
res = Math.max(res, cost(map.get(c), mapPreSum.get(c), m));
}
System.out.println(res);
}
static int cost(List<Integer> position, List<Integer> preSum, int m) {
int res = 0;
int left = 0, right = 0;
while (right < position.size()) {
int mid = left + (right - left + 1) / 2;
int sumA = cost(position, preSum, left, mid, true);
int sumB = cost(position, preSum, mid, right, false);
int cost = sumB - sumA;
if (cost <= m) {
res = Math.max(res, right - left + 1);
right++;
} else left++;
}
return res;
}
static int cost(List<Integer> pos, List<Integer> preSum, int left, int right, boolean isLeft) {
int count = right - left + 1;
int sum = left == 0 ? preSum.get(right) : preSum.get(right) - preSum.get(left - 1);
int move;
if (isLeft) {
int rightPos = pos.get(right);
move = (rightPos + (rightPos - count + 1)) * count / 2;
} else {
int leftPos = pos.get(left);
move = (leftPos + (leftPos + count - 1)) * count / 2;
}
return sum - move;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)