Advertisement
Dmaxiya

字母交换 - 通过代码

Aug 15th, 2022
515
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.47 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         while (sc.hasNext()) {
  7.             String S = sc.next();
  8.             int n = sc.nextInt();
  9.             System.out.println(getMaxLength(S, n));
  10.         }
  11.     }
  12.  
  13.     private static int getMaxLength(String s, int n) {
  14.         ArrayList<ArrayList<Integer>> index = new ArrayList<>();
  15.         for (int i = 0; i < 26; ++i) {
  16.             index.add(new ArrayList<>());
  17.         }
  18.  
  19.         for (int i = 0; i < s.length(); i++) {
  20.             char ch = s.charAt(i);
  21.             index.get(ch - 'a').add(i);
  22.         }
  23.  
  24.         int ans = 0;
  25.         for (int i = 0; i < 26; i++) {
  26.             for (int j = 0; j < index.get(i).size(); j++) {
  27.                 for (int k = j + 1; k <= index.get(i).size(); ++k) {
  28.                     if (judge(index.get(i), j, k, n)) {
  29.                         ans = Math.max(ans, k - j);
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.         return ans;
  35.     }
  36.  
  37.     private static boolean judge(ArrayList<Integer> index, int from, int end, int n) {
  38.         int mid = (from + end - 1) / 2;
  39.         int left = index.get(mid) - (end - from - 1) / 2;
  40.         int dis = 0;
  41.         for (int i = 0; i < end - from; ++i) {
  42.             int target = left + i;
  43.             int origin = index.get(i + from);
  44.             dis += Math.abs(target - origin);
  45.         }
  46.         return dis <= n;
  47.     }
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement