4 lines Python


  • 54

    Update:

    As pointed out by @hayleyhu, I can just take the first too rare character instead of a rarest. Submitted once, accepted in 48 ms.

    def longestSubstring(self, s, k):
        for c in set(s):
            if s.count(c) < k:
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)
    

    Original:

    def longestSubstring(self, s, k):
        if len(s) < k:
            return 0
        c = min(set(s), key=s.count)
        if s.count(c) >= k:
            return len(s)
        return max(self.longestSubstring(t, k) for t in s.split(c))
    

    If every character appears at least k times, the whole string is ok. Otherwise split by a least frequent character (because it will always be too infrequent and thus can't be part of any ok substring) and make the most out of the splits.

    As usual for Python here, the runtime varies a lot, this got accepted in times from 32 ms to 74 ms.


  • 0
    L

    @StefanPochmann Very smart!!!!! It is basically backtracking right? The worst case is O(n^2) .


  • 1

    @lzlmike I don't think it's backtracking. And while it is O(n^2), it's also O(n).


  • 2
    S

    Similarly I solved using Java.

    int max = 0;
    int[] counts = new int[26];
    Set<Character> sets = new HashSet<>();
    Queue<Point> Q = new LinkedList<>();
    Q.offer(new Point(0, s.length()));
    while (!Q.isEmpty()) {
        	Arrays.fill(counts, 0);
            sets.clear();
            
            Point p = Q.poll();
            
            for (int i = p.x; i < p.y; i++) counts[s.charAt(i) - 'a']++;
            for (int i = 0; i < counts.length; i++)
            	if (counts[i] != 0 && counts[i] < k)
            		sets.add((char)(i + 'a'));
    
            if (sets.isEmpty()) {
            	max = Math.max(max, p.y - p.x);
            } else {
            	int start = p.x;
            	for (int i = p.x; i < p.y; i++) {
            		char c = s.charAt(i);
            		if (sets.contains(c)) {
            			if (i != start) {
            				Q.offer(new Point(start, i));
            			}
            			start = i + 1;
            		}
            	}
            	if (start != p.y) {
            		Q.offer(new Point(start, p.y));
            	}
            }
        }
        return max;

  • 0
    W
    This post is deleted!

  • 1
    H

    java solution based on your brilliant idea:

    '''
    public int longestSubstring(String s, int k) {

        if (s.length() == 0 || k == 1) return s.length();
        if (s.length() < k) return 0;
        
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c-'a'] ++;
        boolean eligible = true;
        for (int i = 0; i < 26; i ++) {
            if (count[i] != 0 && count[i] < k) {eligible = false;break;}
        }
        if (eligible) return s.length();
        char least = 0;
        for (int i = 0; i < 26; i ++) {
            if (count[i] != 0 && least == 0) {least = (char)(i+'a');continue;} 
            if (count[i]!=0 && count[i] < count[least - 'a']) least = (char)(i+'a');
        }
        String[] sub = s.split(least+"");
        int res = 0;
        for (String str : sub) {
            res = Math.max(res, longestSubstring(str, k));
        }
        return res;
    }
    

    '''


  • 1
    W

    @StefanPochmann

    Your solution looks like O(n log n) based on the master's theorem on the following recurrence.

    T(n) = b T( N/b ) + O(n)

    The only reason you can say it's O(n) is because there is a fixed-size alphabet limiting the depth to 26, but practically speaking that's equivalent to saying that the algorithm behaves like O(n lg n) up to n< 2^26 or 67,108,864 elements. But then you can say O( n |A| ) where A is the alphabet used in the string.

    So, it's O( n min( lg n, |A| ) )


  • 0

    @wesnerm Yes, with an unlimited alphabet it wouldn't be O(n). Wouldn't be O(n log n) or O(n^2), either, though. Would be O(n^3). Good thing the alphabet does have a fixed and even rather small size :-P


  • 0
    W

    @StefanPochmann

    Each level of recursion is O(n) across all invocations at the same level. Maximum depth is n.
    I don't see how the runtime is cubic.

    It's easy to show quadratic with this example aaaaaabcdefghijklmnopqrstuvwxyz....


  • 0

    @wesnerm min(set(s), key=s.count) would be quadratic (if the alphabet were unlimited).


  • 0
    P

    Could you add cases like baaabcb, 3? Since current cases can all pass sliding window solution, which is wrong.


  • 1
    C

    A small improvement is to handle all characters with frequency less than k at once for each recursive level, but the time complexity won't change too much, for example aaabbbacccbdc, 4.

    And I guess this will make your code longer though.


  • 0

    @pushazhiniao said in 6 lines Python:

    Could you add cases like baaabcb, 3? Since current cases can all pass sliding window solution, which is wrong.

    I can't, but we can suggest it to @1337c0d3r who can :-)

    Can you link to such a solution that fails this case?


  • 1

    @pushazhiniao said in 6 lines Python:

    Could you add cases like baaabcb, 3?

    Done.


  • 0
    L

    @StefanPochmann I just fixed the typo in sliding window way, passed all test cases :)


  • 0
    N

    @lzlmike where is it?


  • 0

  • 17
    H

    Only 7ms for Java solution without looking for the least occurred character, i.e., split the string by any character that doesn't appear for k times.

    public class Solution {
        public int longestSubstring(String s, int k) {
            int n = s.length();
            if (n==0 || n<k) return 0;
            if (k==1) return n;
            int[] counts = new int[26];
            for (char c: s.toCharArray()) counts[c-'a']++;
            boolean valid = true;
            char badchar = 0;
            for (int i=0; i<26; i++) {
                if (counts[i]>0 && counts[i]<k) {
                    badchar = (char)(i+'a');
                    break;
                }
            }
            if (badchar==0) return n;
            String[] subs = s.split(badchar+"");
            int res = 0;
            for (String sub:subs) res = Math.max(res, longestSubstring(sub,k));
            return res;
        }
    }
    

  • 0

    @hayleyhu Thanks, that allowed me to save two lines :-) See my update.


  • 0

    @StefanPochmann said in 4 lines Python:

    @wesnerm Yes, with an unlimited alphabet it wouldn't be O(n). Wouldn't be O(n log n) or O(n^2), either, though. Would be O(n^3).

    Stefan, how did you derive that O(n^3) bound? Could you elaborate more on that? Thanks. Also, why do you think that your 4-line solution is O(n)? Just want to confirm I'm on the right track. Thanks.


Log in to reply
 

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