Java D & C Solution


  • 10
    C

    The idea is pretty basic, find the point where we should split the string, eg, the position of character which total count is <k, then dfs it then find the max.
    For Example: bbcddefegaghfh and 2, so we shall dfs on "bb", "ddefeg", "ghfh", since a , c only appears1 for once.

    public int longestSubstring(String s, int k) {
           if (s == null || s.length() == 0 || k == 0) return 0;
           int max = 0;
           int[] count = new int[26];
           int res = 0;
           for (int i = 0; i < s.length(); i++) {
               count[s.charAt(i) - 'a']++;
           }
           List<Integer> pos = new ArrayList<Integer>();
           for (int i = 0; i < s.length(); i++) {
               if (count[s.charAt(i) - 'a'] < k) pos.add(i);
           }
           if (pos.size() == 0) return s.length();
           pos.add(0, -1);
           pos.add(s.length());
           for (int i = 1; i < pos.size(); i++) {
               int start = pos.get(i-1) + 1;
               int end = pos.get(i);
               int next = longestSubstring(s.substring(start, end), k);
               res = Math.max(res, next);
           }
           return res;
       }
    

  • 0
    S

    @curt Can you explain me the time complexity of this algorithm?


Log in to reply
 

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