fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static class OrderedMultiSet<E extends Comparable<E>> {
  6.         private final TreeMap<E, Integer> freqMap;
  7.  
  8.         public OrderedMultiSet() {
  9.             freqMap = new TreeMap<>();
  10.         }
  11.  
  12.         public void insert(E val) {
  13.             freqMap.put(val, freqMap.getOrDefault(val, 0) + 1);
  14.         }
  15.  
  16.         public void erase(E val) {
  17.             if (freqMap.containsKey(val)) {
  18.                 int cnt = freqMap.get(val);
  19.                 if (cnt > 1) {
  20.                     freqMap.put(val, cnt - 1);
  21.                 } else {
  22.                     freqMap.remove(val);
  23.                 }
  24.             }
  25.         }
  26.  
  27.         public E min() {
  28.             return freqMap.firstKey();
  29.         }
  30.  
  31.         public E max() {
  32.             return freqMap.lastKey();
  33.         }
  34.  
  35.         public Iterator<E> iterator() {
  36.             return new Iterator<E>() {
  37.                 private final Iterator<Map.Entry<E, Integer>> itr = freqMap.entrySet().iterator();
  38.  
  39.                 @Override
  40.                 public boolean hasNext() {
  41.                     return itr.hasNext();
  42.                 }
  43.  
  44.                 @Override
  45.                 public E next() {
  46.                     return itr.next().getKey();
  47.                 }
  48.             };
  49.         }
  50.     }
  51.  
  52.     public static void main(String[] args) {
  53.         Scanner in = new Scanner(System.in);
  54.         int length = in.nextInt();
  55.         int limit = in.nextInt();
  56.         in.nextLine();
  57.         String str = in.nextLine();
  58.  
  59.         OrderedMultiSet<Character> window = new OrderedMultiSet<>();
  60.         int bestLen = 0;
  61.         int leftPtr = 0;
  62.  
  63.         for (int rightPtr = 0; rightPtr < length; rightPtr++) {
  64.             window.insert(str.charAt(rightPtr));
  65.             while (window.max() - window.min() > limit) {
  66.                 window.erase(str.charAt(leftPtr));
  67.                 leftPtr++;
  68.             }
  69.             bestLen = Math.max(bestLen, rightPtr - leftPtr + 1);
  70.         }
  71.  
  72.         System.out.println(bestLen);
  73.     }
  74. }
  75.  
Success #stdin #stdout 0.13s 56812KB
comments (?)
stdin
copy 
5 2
abdzd
stdout
copy 
2
https://ideone.com/VKPnVK
language:
Java (HotSpot 12)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!