ven4coding

Longest Substring with K distinct characters Optimized

Sep 26th, 2021
1,105
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. class LongestSubstringKDistinct {
  4.   public static int findLength(String str, int k) {
  5.     // TODO: Write your code here
  6.     // map to store count.
  7.     Map<Character, Integer> map = new HashMap<>();
  8.     int maxLength = 0;
  9.     int windowStart = 0;
  10.     for(int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
  11.       char rightChar = str.charAt(windowEnd);
  12.       // store character count in map
  13.       map.put(rightChar, map.getOrDefault(rightChar, 0)+1);
  14.       // compare mapsize with k and loop till mapsize less than or equal to k
  15.       while(map.size() > k) {
  16.         // shrink by examining right character.
  17.         char leftChar = str.charAt(windowStart);
  18.         // reduce leftChar len and remove if len is 0
  19.         map.put(leftChar, map.get(leftChar)-1);
  20.         if(map.get(leftChar) == 0) {
  21.           map.remove(leftChar);
  22.         }
  23.         // slide to right.
  24.         windowStart++;
  25.       }
  26.  
  27.       maxLength = Math.max(maxLength, windowEnd-windowStart + 1);
  28.     }
  29.     return maxLength;
  30.   }
  31. }
  32.  
RAW Paste Data