Easy to understand Java solution with explanation


  • 0
    O
    public class Solution {
        
        class DistinctSubstring {
            // a map recording latest char - index map
            protected Map<Character, Integer> map;
            
            protected int k;
            
            protected int startIdx;
            
            protected int endIdx;
            
            protected String s;
            
            public DistinctSubstring(String s, int k) {
                this.map = new HashMap<>();
                this.k = k;
                this.startIdx = 0;
                this.endIdx = 0;
                this.s = s;
            }
            
            public boolean couldAppend(char c) {
                return map.size() < k || map.containsKey(c);
            }
            
            public void append(char c, int idx) {
                this.map.put(c, idx);
                this.endIdx = idx;
            }
            
            public void remove() {
                int newStartIdx = s.length() - 1;
                Character charToRemove = null;
                for(char c: map.keySet()) {
                    int idx = map.get(c);
                    if(idx < newStartIdx) {
                        newStartIdx = idx;
                        charToRemove = c;
                    }
                }
                // +1 to exclude this char
                this.startIdx = newStartIdx + 1;
                this.map.remove(charToRemove);
            }
            
            
            public int getLength() {
                return endIdx - startIdx + 1;
            }
        }
        
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            if(k == 0) return 0;
            int maxLen = 0;
            DistinctSubstring ds = new DistinctSubstring(s, k);
            for(int i = 0; i < s.length();) {
                char c = s.charAt(i);
                if(ds.couldAppend(c)) {
                    ds.append(c, i);
                    i ++;
                } else {
                    ds.remove();
                }
                maxLen = Math.max(maxLen, ds.getLength());
            }
            return maxLen;
        }
    }
    

    Update logic:

    1. If there aren't more than k distinct characters in DistinctSubstring, simple add the char and its index into the map.
    2. If there are already k distinct characters, iterate the map to find the front-most character in the string, set the start index as this index + 1. That operation means this character is removed from substring.

    In order to do so, we maintain a map for character - index mapping, as well as a start index and end index for the substring.

    Firstly iterate the input string, when there aren't enough distinct characters or this character is contained in the map, we simple update the map with its latest index. In this way we can guarantee the index in this map indicates the potential start of the substring.

    Since we are removing some character when the input string iterator sees a new character, the startIdx should be the least one in the map, excluded.

    Updating endIdx is easy, each time we successfully append a character, we update the endIdx.


Log in to reply
 

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