Java recursive solution, average O(nlogn), worst O(n^2)


  • 0
    D

    Whenever we found a character that occurs less than k times in the range, we know that the solution sub-string won't cross this character. So the problem can be divided into non-overlapping sub-problems.

    In the average case, because we divide evenly, so T(n) = s * T(n/s) + n and T(n) = O(nlogn); if we divide very pathologically, then T(n) = T(n - 2) + n, so T(n) = O(n^2).

    public class Solution {
        public int longestSubstring(String s, int k) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            return longestSubstring(s, k, 0, s.length() - 1);
        }
        
        private int longestSubstring(String s, int k, int bIndex, int eIndex) {
            if (bIndex > eIndex) {
                return 0;
            }
            Map<Character, Integer> count = new HashMap<>();
            for (int i = bIndex; i <= eIndex; i++) {
                char ch = s.charAt(i);
                count.put(ch, count.containsKey(ch) ? count.get(ch) + 1 : 1);
            }
            int ret = -1;
            int p = bIndex;
            int selfLen = eIndex - bIndex + 1;
            while (p <= eIndex) {
                int q = p;
                for (; q <= eIndex && count.get(s.charAt(q)) >= k; q++) {}
                if (q - p < selfLen) {
                    ret = Math.max(ret, longestSubstring(s, k, p, q - 1));
                }
                p = q + 1;
            }
            return ret == -1 ? selfLen : ret;
        }
    }
    

Log in to reply
 

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