15 lines java solution using slide window


  • 63
    J

    feel it is not a new question, just use num to track the number of distinct characters within the slide window

    public class Solution {
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            int[] count = new int[256];
            int num = 0, i = 0, res = 0;
            for (int j = 0; j < s.length(); j++) {
                if (count[s.charAt(j)]++ == 0) num++;
                if (num > k) {
                    while (--count[s.charAt(i++)] > 0);
                    num--;
                }
                res = Math.max(res, j - i + 1);
            }
            return res;
        }
    }

  • 55
    Y

    A more generic solution as follows, can be solution for Unicode string:

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int best = 0;
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
            while (map.size() > k) {
                char leftChar = s.charAt(left);
                if (map.containsKey(leftChar)) {
                    map.put(leftChar, map.get(leftChar) - 1);                     
                    if (map.get(leftChar) == 0) { 
                        map.remove(leftChar);
                    }
                }
                left++;
            }
            best = Math.max(best, i - left + 1);
        }
        return best;
    } 

  • 0
    L

    good idear!!!!!!


  • 3
    C

    @yfcheng
    I think "if (map.containsKey(leftChar))" condition check is redundant here.


  • 0
    J

    One optimization, update the res only when valid substring beginning at i reaches the longest:

    • Put update of res, i.e. res = Math.max(res, j - i + 1), into the if statement, just above the while loop. Replace it by res = Math.max(res, j - i). This is the place where a valid substring grows to the greatest.
    • Put another update for res before return statement, i.e. res = Math.max(s.length() - i, res).

    This optimization is very general, it avoids unnecessary updates.


  • 13
    N

    @jiangbowei2010 IMHO I am not a big fan of reducing lines of code just for the sake of it. I would rather write 10 more lines of code that makes it more readable and understandable.


  • 1
    M

    @jiangbowei2010 Perfect elegant code. Array is more efficient than map


  • 0
    F
    This post is deleted!

  • 7
    R

    Completely agreed with nosyDev. If I were the interviewer you would lose some points for collapsing many instructions in a single line. This makes the code not only hard to understand, also prone to nasty bugs, hard to debug, log, etc.
    Unfortunately, this is the general tendency on leetcode, for some reason most people think making the code shorter is more important than making it easily understandable.


  • 16
    A

    Simplified the code a bit. Made the sliding window a bit more readable :)

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int[] count = new int[256];     // there are 256 ASCII characters in the world
        
        int i = 0;  // i will be behind j
        int num = 0;
        int res = 0;
        
        for (int j = 0; j < s.length(); j++) {
            if (count[s.charAt(j)]++ == 0) {    // if count[s.charAt(j)] == 0, we know that it is a distinct character
                num++;
            }
            while (num > k && i < s.length()) {     // sliding window
                count[s.charAt(i)]--;
                if (count[s.charAt(i)] == 0){ 
                    num--;
                }
                i++;
            }
            res = Math.max(res, j - i + 1);
        }
        return res;
    }
    

  • 0

    @nosyDev Agree that readability is in the first place. But it depends. Longer doesn't always mean more readable.


  • 0

    @yfcheng Thanks for sharing! How about using remove() to simplify the while body like this?

                while (cnt.size() > k) {
                    if (!cnt.remove(c[from], 1)) // If val=1, remove key-val pair. Otherwise, decrement by 1
                        cnt.put(c[from], cnt.get(c[from]) - 1);
                    from++;
                }
    

  • 0
    1

    Does anyone analyze the time complexity of this solution?


  • 0

    @jiangbowei2010 cool! I modified your code into HashMap style:

    import java.util.*;
    
    public class Solution {
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            Map<Character, Integer> map = new HashMap<Character, Integer>();
            int leftIndex = 0, res = 0;
            char[] cs = s.toCharArray();
            for (int rightIndex = 0; rightIndex < cs.length; rightIndex++) {
                if (map.get(cs[rightIndex]) == null) map.put(cs[rightIndex], 1);
                else map.put(cs[rightIndex], map.get(cs[rightIndex]) + 1);
                if (map.size() > k) {
                    while (leftIndex++ < cs.length && map.get(cs[leftIndex - 1]) != null && map.get(cs[leftIndex - 1]) - 1 > 0)
                        map.put(cs[leftIndex - 1], map.get(cs[leftIndex - 1]) - 1);
                    map.remove(cs[leftIndex - 1]);
                }
                res = Math.max(res, rightIndex - leftIndex + 1);
            }
            return res;
        }
    }
    

    But yours is more decent @yfcheng


  • 0

    @jiangbowei2010 said in 15 lines java solution using slide window:

    feel it is not a new question, just use num to track the number of distinct characters within the slide window

    public class Solution {
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            int[] count = new int[256];
            int num = 0, i = 0, res = 0;
            for (int j = 0; j < s.length(); j++) {
                if (count[s.charAt(j)]++ == 0) num++;
                if (num > k) {
                    while (--count[s.charAt(i++)] > 0);
                    num--;
                }
                res = Math.max(res, j - i + 1);
            }
            return res;
        }
    }
    

    Thanks for your idea, I improved your solution beating 98.03% by indexing a character in a char[] array instead of a string using s.charAt(i);
    https://discuss.leetcode.com/topic/83261/share-my-java-solution-using-slide-window-beating-98-03-inspired-by-jiangbowei2010


  • 0

    Slightly different code writing using while loop and hashmap, which is more readable.

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
            Map<Character, Integer> map = new HashMap<>();
            int lo=0;
            int hi=0;
            while(hi<s.length()) {
                map.put(s.charAt(hi), map.getOrDefault(s.charAt(hi),0)+1);
                if(map.size()>k) { // need to slide
                    if(map.get(s.charAt(lo))==1)
                        map.remove(s.charAt(lo));
                    else
                        map.put(s.charAt(lo), map.get(s.charAt(lo))-1);
                    lo++;
                    hi++;
                } else { // need to extend
                    hi++;
                }
            }
            return hi-lo;
        }

  • 0
    M

    @yfcheng You don't need to check if (map.containsKey(leftChar)) because it will always contain the character for the past one. I removed this line and passed.


  • 0
    H

    @1276stella O(n^2)


  • 0
    H

    @Hack3r No, this is O(n). each node is only added or removed for once.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.