Simple JAVA O(n) Solution


  • 3

    The exact time complexity is O(26n) = O(n), where n is the length of the input string.
    The proof is simply that every time, we remove a letter (all of that one) from string (or sub-string). So the maximum level of recursion tree is 26, since there are only 26 letters in this case. And at each level, the total characters we need process are no more than n. Thus, the time complexity is O(n).

    Visualization:

    [00000000000000000000000000] number of kinds of letters remained: no more than L (L<=26);
    [000000000].....[000000]...[00000] number of kinds of letters remained no more than L-1;
    ...
    ...
    ...

    So the total level is no more than 26;

    public int longestSubstring(String s, int k) {
            int[] map = new int[26];
            for(int i=0;i<s.length();i++) {
                map[s.charAt(i)-'a']++;
            }
            char noChar = 'a';
            boolean containsNoChar = false;
            for(int i=0;i<26;i++) {
                noChar = (char)('a'+i);
                if(map[i]<k&&map[i]!=0) {
                    containsNoChar = true;
                    break;
                }
            }
            if(containsNoChar==false) return s.length();
            int ans = 0;
            int start = 0;
            while(s.indexOf(noChar, start)!=-1) {
                int end = s.indexOf(noChar, start);
                ans = Math.max(ans, longestSubstring(s.substring(start,end), k));
                start = end + 1;
            }
            ans = Math.max(ans, longestSubstring(s.substring(start,s.length()), k));
            return ans;
        }
    

  • 0
    L

    Judging from what you wrote, I didn't see an O(n) solution. Your answer is simply a divide and conquer recursion. Best case O(n) and worst case O(n^2). Your version (7ms) is even slower than other split recursion, which is usually 4ms.


  • 0

    @ming58 the cap of the algorithm is O(26n). How can you get a O(n^2) case from this algorithm (n>26)?


  • 0
    L

    @tjcd It is not O(n) .... you are writing recursion, it's T(n) = kT(n/k) + n. Can't be O(n). It is just divide and conquer way. Most people wrote this recursion, but it's about O(nlogn) by master theorem, maybe even worse.


  • 0
    L
    This post is deleted!

  • 0

    @lzlmike it's not T(n) = kT(n/k) + n. If you want a recursion equation, it's T(n) = kT((n-k)/k) + n - k, where k is the number of one curtain letter in that string. Every time I remove one letter (all letters of that one) from string, the max level is 26 not log(n)/log(k). Draw recursion tree yourself to see if it is the case.


  • 0

    @LeoM58 ....I did remove noChar, noChar is located at end, not start.


  • 0
    L

    One simple question, you iterate the string twice every invoke, how come you get to O(26n)? Shouldn't it be O(52n) if we assume you were right?


  • 0
    L

    @tjcd let's say the length is n, in the first loop you write, it is from 0->n, after the first recursion, assume the length is about n - 2, loop 0 -> n - 1, then another recursion 0 -> n -2 ....... you loops 1 + 2 + ... + n - 1 + n = n(n - 1) /2 which is n^2 in worst case


  • 1

    @LeoM58 well both of us are right, O(n) =O(26n)=O(52n). constant doesn't matter


  • 0

    @lzlmike Not just one letter but all of that one letter will be removed after each resursion.


  • 0
    L

    @tjcd But what if there is only one letter removed each recursion


  • 0

    @lzlmike then n<=26, my analysis is still right.


  • 0

    @tjcd
    You called indexOf(). That function itself is O(n) not O(1). And you put it into a O(n) loop. So it is O(n^2).


  • 0

    @Nakanu Sigh.. like I said, if you can draw correct recursion tree, you will see what I meant. And computing time complexity is not simply saying that "you have an O(n) loop and each loop you do O(n) and you gonna have O(n^2) for total" sometime it is the case but sometime it isn't. it's not simply multiplication and you need break it down into levels of recursion and add them up. The funny thing is this solution is O(n) believe it or not.


Log in to reply
 

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