Java 53 ms, O(N) time, O(N) space solution


  • 0
    F
    
    public class Solution {
        // interval overlapping algorithm, or frog jumpping algorithm
        private int lastlen(List<List<Integer>> lists, int k){
    
            int start = -1;
            Set<Integer> set = new HashSet<>();
            for(int i = 0; i < lists.size(); i++) {
                List<Integer> list = lists.get(i);
                if (list != null && list.size() < k) {
                    start = Math.max(start, list.get(list.size() - 1));
                }else if(list != null){
                    set.add(i);
                }
            }
    
            boolean exists = true;
            while(exists){
                exists = false;
                Iterator<Integer> it = set.iterator();
                while(it.hasNext()){
                    List<Integer> list = lists.get(it.next());
                    int size = list.size();
                    if(list.get(size - k) < start){
                        start = Math.max(start, list.get(size - 1));
                        exists = true;
                        it.remove();
                    }
                }
            }
    
            return start;
        }
    
        public int longestSubstring(String s, int k){
    
            int res = 0;
            List<List<Integer>> indices = new ArrayList<>();
            for(int i = 0; i < 26; i++){
                indices.add(null);
            }
            for(int i = 0; i < s.length(); i++){
                int ind = (int)(s.charAt(i) - 'a');
                if(indices.get(ind) == null)
                    indices.set(ind, new ArrayList<Integer>());
                indices.get(ind).add(i);
                res = Math.max(i - lastlen(indices, k), res);
            }
    
            return res;
    
        }
    

  • 0
    F

    A somewhat optimized version:

    public class Solution {
    
        private int lastlen(Map<Character, Deque<Integer>> lists, int k){
    
            int start = -1;
            Set<Character> set = new HashSet<>();
            for(Character c : lists.keySet()) {
                Deque<Integer> list = lists.get(c);
                if (list != null && list.size() < k) {
                    start = Math.max(start, list.getLast());
                }else{
                    set.add(c);
                    while(list.size() > k){
                        list.remove();
                    }
                }
            }
    
            boolean exists = true;
            while(exists){
                exists = false;
                Iterator<Character> it = set.iterator();
                while(it.hasNext()){
                    Deque<Integer> list = lists.get(it.next());
                    int size = list.size();
                    if(list.peekFirst() < start){
                        start = Math.max(start, list.peekLast());
                        exists = true;
                        it.remove();
                    }
                }
            }
    
            return start;
        }
    
        public int longestSubstring(String s, int k){
    
            int res = 0;
            Integer start = null;
            Map<Character, Deque<Integer>> indices = new HashMap<>();
            for(int i = 0; i < s.length(); i++){
                Character c = s.charAt(i);
                Deque<Integer> q = indices.get(c);
                if(q == null)
                    indices.put(c, q=new ArrayDeque<Integer>());
                q.offer(i);
                if(start != null && q.size() >= k && q.getFirst() > start);
                else{
                    start = lastlen(indices, k);
                }
                res = Math.max(i - start, res);
            }
    
            return res;
    
        }
    }
    

  • 0
    F

    Also a binary search algorithm, len = s.length()/2, check whether some substring with len satisfies the condition, if not, then len = s.length()/4; if so, len = 0.75*s.length();


Log in to reply
 

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