Share my Java solution using slide window beating 98.03% inspired by @jiangbowei2010


  • 2
    public class Solution {
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            int[] count = new int[256];
            char[] cs = s.toCharArray();
            int distinctNum = 0, leftI = 0, res = 0;
            for (int rightI = 0; rightI < cs.length; rightI++) {
                if (count[cs[rightI]]++ == 0) distinctNum++;
                if (distinctNum > k) {
                    while (--count[cs[leftI++]] > 0);
                    distinctNum--;
                }
                res = Math.max(res, rightI - leftI + 1);
            }
            return res;
        }
    }
    

    Submission link: https://leetcode.com/submissions/detail/97037506/
    beating 98.03%
    0_1491001787639_Screen Shot 2017-03-31 at 5.08.59 PM.png

    Inspired by https://discuss.leetcode.com/topic/41671/15-lines-java-solution-using-slide-window
    I made two improvements:

    1. Used char[] array for indexing a character instead of doing that in a substring. For instance, used
    cs[rightI]
    

    instead of

    s.charAt(rightI)
    
    1. Renamed variable to made the code easier to understand
      The variables below are the same meaning:
      num, distinctNum: number of distinct characters inside the slide window
      i, leftI: left index of the slide window
      j, rightI: right index of the slide window
    num, i, j
    
    distinctNum, leftI, rightI
    
    public class Solution {
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            int[] count = new int[256];
            int distinctNum = 0, leftI = 0, res = 0;
            for (int rightI = 0; rightI < s.length(); rightI++) {
                if (count[s.charAt(rightI)]++ == 0) distinctNum++;
                if (distinctNum > k) {
                    while (--count[s.charAt(leftI++)] > 0);
                    distinctNum--;
                }
                res = Math.max(res, rightI - leftI + 1);
            }
            return res;
        }
    }
    

    submission link:
    https://leetcode.com/submissions/detail/97037987/
    beating 80.86%
    author: @jiangbowei2010


Log in to reply
 

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