Java--new idea, easy to understand


  • 0
    G

    We use set to record those character shown up less than K times.
    We use List[26] to record all the index of each character.
    Set.remove(**) means letter ** shows up for K times. At this time, for those letters in set, if their last show up'index less than **'s first show up. We update maxLen.
    Here is the code.

    public int longestSubstring(String s, int k) {
        if(s == null || s.length() == 0)  return 0;
        HashSet<Character> set = new HashSet<>();
        List<Integer>[] table = new List[26];
        int[] count = new int[26];
        int maxLen = 0;
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(table[ch - 'a'] == null)  table[ch - 'a'] = new ArrayList<>();
            if(table[ch - 'a'].size() == k)  table[ch - 'a'].remove(0);
            table[ch - 'a'].add(i);
            if(++count[ch - 'a'] < k) {
                set.add(ch);
            } else {
                set.remove(ch);
                int start = -1;
                // if set is empty, len = i - (-1), so we should initialize start as -1.
                for(Character item: set) {
                    int num = item - 'a';
                    if(table[num].get(table[num].size() - 1) > table[ch - 'a'].get(0))  start = i;
                    // like ababa, first a is before than first b, 
                   // so there is no maxLen candidate,  set start = i
                    
                    start = Math.max(start, table[num].get(table[num].size() - 1));
                }
                maxLen = Math.max(maxLen, i - start);
            }
        }
        return maxLen;
    }

Log in to reply
 

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