Java AC solution


  • 0

    The idea is scanning through the whole string, find all characters not appearing k times. These characters separate the string into several substrings. Recurring applying the method, finding the largest length.

        public int longestSubstring(String s, int k) {
            return largest(s, k);        
        }
        private int largest(String s, int k) {
            if (s.length() < k) return 0;
            HashMap<Character, ArrayList<Integer>> hash = new HashMap<Character, ArrayList<Integer>>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (!hash.containsKey(c)) hash.put(c, new ArrayList<Integer>());
                hash.get(c).add(i);
            }
            boolean[] cuts = new boolean[s.length()];
            for (ArrayList<Integer> list: hash.values()) {
                if (list.size() >= k) continue;
                for (int n: list) {
                    //System.out.println(n);
                    cuts[n] = true;
                }
            }
            int last = 0;
            int i = 0;
            int max = 0;
            while (i < cuts.length) {
                if (!cuts[i]) i++;
                else {
                    max = Math.max(max, largest(s.substring(last, i), k));
                    while (i < cuts.length && cuts[i]) i++;
                    last = i;
                }
            }
            if (last == 0) max = s.length();
            else max = Math.max(max, largest(s.substring(last, s.length()), k));
            
            return max;
        }

Log in to reply
 

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