Naive Java Solution18ms with sliding window technique.


  • 0
    Z

    The worst case performance seems to be O(26n^2) but it runs faster than some O(26n) solutions. Is the reason weak test cases?

    public class Solution {

    public int longestSubstring(String s, int k) {
        if(s.isEmpty()) return 0;
        int ans = 0;
        int a[][] = new int[s.length()][26];
        a[0][s.charAt(0)-'a']++;
        for(int i = 1;i<s.length();i++){
            int ch = s.charAt(i)-'a';
            for(int j = 0;j<ch;j++){
                a[i][j] = a[i-1][j];
            }
            a[i][ch] = a[i-1][ch]+1;
            for(int j = ch+1;j<26;j++){
                a[i][j] = a[i-1][j];
            }
        }
        
        int l = k;
        int r = s.length();
        for(int m =r;m>=l;m--){
            if(isValid(k,a,s,m)) {
                ans = m;
                break;
            }
        }
        
        return ans;
    }
    
    public boolean isValid(int k,int a[][], String s, int m){
        for(int i = 0;i<=s.length()-m;i++){
            boolean ok =  true;
            for(int j = 0;j<26;j++){
                int num  = (i==0)?a[i+m-1][j]:a[i+m-1][j]-a[i-1][j];
                if(num!=0 && num<k){
                    ok =  false;
                    break;
                }
            }
            if(ok) return true;
        }
        return false;
    }
    

    }


Log in to reply
 

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