Java divide and conquer(recursion) solution


  • 49
    public int longestSubstring(String s, int k) {
        char[] str = s.toCharArray();
        return helper(str,0,s.length(),k);
    }
    private int helper(char[] str, int start, int end,  int k){
        if(end-start<k) return 0;//substring length shorter than k.
        int[] count = new int[26];
        for(int i = start;i<end;i++){
            int idx = str[i]-'a';
            count[idx]++;
        }
        for(int i = 0;i<26;i++){
            if(count[i]<k&&count[i]>0){ //count[i]=0 => i+'a' does not exist in the string, skip it.
                for(int j = start;j<end;j++){
                    if(str[j]==i+'a'){
                        int left = helper(str,start,j,k);
                        int right = helper(str,j+1,end,k);
                        return Math.max(left,right);
                    }
                }
            }
        }
        return end-start;
    }

  • 2
    D

    I rewrite it in C++ and simplify some parts of code.

    class Solution {
    public:
        int longestSubstring(string s, int k) {
            
           return helper(0,s.size()-1, s, k);
            
        }
        int helper(int begin, int end, string & s, int k)
        {
            
            if(end<begin) return 0;
            if(end-begin+1<k) return 0;
            
            vector<int> num_of(26,0);
    
            for(int i=begin; i<=end; i++)
            {
                int idx = s[i] - 'a';
                num_of[idx] ++;
                
            }
    
           int len = end - begin + 1;
    
           for(int j=begin; j<=end; j++)
            {
                if(num_of[s[j] - 'a'] < k)
                {
                    int left = helper(begin,j-1,s,k);
                    int right = helper(j+1, end,s,k);
                    len = max(left, right);
                    return len;
        
                }
                
            }
            return len;
        }
    };
    

  • 2
    Q

    @Nakanu same to you, but with less lines code

        public int longestSubstring(String s, int k) {
            char[] a = s.toCharArray();
            return helper(a, 0, s.length(), k);
        }
        public int helper(char[] a, int st, int en, int k) {
            if(en<=st || k>en-st) return 0;
            int[] cnt = new int[26];
            for(int i=st; i<en; i++) cnt[a[i]-'a']++;
            for(int i=0; i<26; i++) {
                if(cnt[i]==0) continue;
                if(cnt[i] < k) {
                    for(int j=st; j<en; j++) {
                        if(a[j]==i+'a') {
                            return Math.max(helper(a, st, j, k), helper(a, j+1, en, k) );
                        }
                    }
                }
            }
            return en-st;
        }
    

  • 1
    X

    Can anyone explain to me what is the time complexity for this solution? Thanks.


  • 3

    @xiaoyaoworm
    Well. It has been a long time since I wrote this solution.
    First, let us see how does this code work.
    The idea is to keep finding the character which does not satisfy the requirement. (repeat less than k times).
    And divide the problem into 2 parts, to find the longest substring on the lhs and rhs of the breaking point.

    For divide and conquer, it needs O(log(n)) calls of helper function to check the entire string and in the helper function, it costs O(n) to find such breaking point. In total, this algorithm is O(nlog(n)).

    Edit: The analysis was not correct. It should be O(n^2).


  • 15
    W

    Shorter and faster :)
    @quantumlaser, @DecaYale

    int longestSubstring(const string &s, int k) {
        return helper(s, 0, s.size(), k);
    }
    int helper(const string &s, int beg, int end, int k){
        if(end - beg < k) return 0;
        int cnt[26]{};
        for(int i = beg; i < end; ++i) ++cnt[s[i]-'a'];
        for(int i = beg; i < end; ++i)
            if (cnt[s[i] - 'a'] < k)
                return max(helper(s, beg, i, k), helper(s, i + 1, end, k));
        return end - beg;
    }
    

  • 0
    X

    @Nakanu Awesome explanation, thanks!!!


  • 7
    H

    This code is O(n^2), here's an example input:

    k = 5
    a4,b4,c4.......y4,z5 as in "aaaabbbbcccc.........yyyyzzzzz"

    answer: 5 ("zzzzz")


  • 0

    @hide
    This example is sort of worst case for the algorithm. I agree with you.


  • 0
    M

    why do you need the outer loop?

    for (int i = 0; i < 26; i++) {
        ...
    }
    

    this one?

    This is my 4 ms accepted code without it:

    public int longestSubstring(String s, int k) {
        return dc(s, 0, s.length(), k);
    }
        
    public int dc(String s, int start, int end, int k) {
        if (end - start < k) return 0;
        int[] cnt = new int[26];
        for (int i = start; i < end; i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        for (int i = start; i < end; i++) {
            if (cnt[s.charAt(i) - 'a'] < k) {
                return Math.max(dc(s, start, i, k), dc(s, i + 1, end, k));
            }
        }
        return end - start;
    }
    

  • 1
    H

    @marcusgao94 it's not needed, but it makes it less likely that you will split close to the beginning of your 'start' index (which is bad. you want to split in the middle). further proof is that OP's code takes 3ms


  • 0

    Excellent, but i want to know what's the meaning of this sentence:
    if(str[j]==i+'a')


  • 0

    @yaqi13

    For example, 'a'+1 = 'b' .


  • 0
    N

    good thought.

    But you don't need these codes

    1. if(end<start) return 0;
    2. if(count[i]<k&&count[i]>0), then we can skip (count[i]==0)

    Also, no need to change string to char array


  • 0

    @notturno Thank you for your suggestion! Yea, some codes are redundant. I have modified my code.
    For the toCharArray(), I did that cuz it is faster to do it rather than keep calling String.charAt().


  • 24
    G

    In my attempts to understand this clever solution, I refactored it and added some comments:

    This solution uses Strings rather than character arrays, but that's just a personal preference (performance is still 3ms).

    public class Solution {
    
        /**
         * Given a String s and an integer k, return the longest "valid" substring,
         * where a substring is valid iff every character in the substring occurs
         * at least k times.
         * 
         * @param s The given String
         * @param k The minimum number of times all substring characters must occur
         * @return The length of the longest valid substring
         */
        public int longestSubstring(String s, int k) {
    
            // Call divide and conquer helper method
            return div(s, 0, s.length(), k);
        }
        
        /**
         * Determines the length of the longest valid substring.
         * 
         * We achieve this by recursively splitting the given String on characters
         * who do not occur at least k times (since they cannot be part of the
         * longest valid substring).
         * 
         * Note that the substring of the current recursion is always equivalent
         * to s.substring(start, end).  For space reasons, we don't ever actually
         * create a new substring.
         * 
         * @param s The given String
         * @param start The beginning of the substring, inclusive
         * @param end The end of the substring, exclusive
         * @param k The minimum number of times all substring characters must occur
         * @return The length of the longest valid substring
         */
        private int div(String s, int start, int end, int k) {
            
            /**
             * Base Case 1 of 2:
             * 
             * If this substring is shorter than k, then no characters in it
             * can be repeated k times, therefore this substring and all
             * substrings that could be formed from it are invalid,
             * therefore return 0.
             */
            if (end - start < k) return 0;
            
            /**
             * Count the frequency of characters in this substring.
             * 
             * We are guaranteed from the problem statement that the given String
             * can only contain lowercase (English?) characters, so we use a
             * table of length 26 to store the character counts.
             */
            int[] a = new int[26];
            for (int i = start; i < end; i++) {
                a[s.charAt(i)-'a']++;
            }
            
            // For every character in the above frequency table
            for (int i = 0; i < a.length; i++){
                
                /**
                 * If this character occurs at least once, but fewer than k times
                 * in this substring, we know:
                 * (1) this character cannot be part of the longest valid substring,
                 * (2) the current substring is not valid.
                 * 
                 * Hence, we will "split" this substring on this character,
                 * wherever it occurs, and check the substrings formed by that split
                 */
                if (a[i] > 0 && a[i] < k) {
                    
                    /**
                     * Look for each occurrence of this character (i + 'a')
                     * in this substring.
                     */
                    for (int j = start; j < end; j++) {
                        if (s.charAt(j) == i + 'a') {
                            
                            // "Split" into two substrings to solve recursively
                            int l = div(s, start, j, k);
                            int r = div(s, j + 1, end, k);
                            return Math.max(l, r);
                        }
                    }
                }
            }
            
            /**
             * Base Case 2 of 2:
             * 
             * If every character in this substring occurs at least k times,
             * then this is a valid substring, so return this substring's length.
             */
            return end - start;
        }
    }
    

  • 0
    H
    This post is deleted!

  • 0
    S

    @hide I think it's O(n^3) for your example? n iteration, n dividing ways, n letter to scan for each dividing.


  • 0
    H

    @shadowless The n iteration + n letter to scan should be 2n, which equal to n not n^2. Plus the n dividing ways, I think total running time still should be O(n^2).


  • 0
    J

    Now, It has 28 test cases but the runtime is 105ms. not sure how many test cases there were.


Log in to reply
 

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