O(N) time, O(N) space Java


  • 0
    M

    The idea is to keep the character appearance at every position from left to right.

    At every position, assume it is the end of the substring we are looking for, find those characters the appearance <k, then set the start as the position that after it, those <k characters never appear. Finally we check if from start to end, it is a legal substring (all characters appear >=k times). Because we keep the snapshots at every position, all these steps can be done in O(26), which is O(1).

    public class Solution {
        public int longestSubstring(String s, int k) {
            int len = s.length(), lastAppear[] = new int[26], total[] = new int[26], snapshots[][] = new int[len][], max = 0;
            Arrays.fill(lastAppear, -1);
        
            for(int i = 0; i<len; i++) {
                int idx = s.charAt(i)-'a', start = -1;
            
                total[idx]++;
                snapshots[i] = total.clone();
                lastAppear[idx] = i;
            
                if(total[idx]<k) continue;
            
                for(int j = 0; j<26; j++) {
                    if(snapshots[i][j]<k) start = Math.max(start, lastAppear[j]);
                }
            
                if(i-start<=max) continue;
            
                boolean legal = true;
                for(int j = 0; j<26 && legal; j++) {
                    int dif = snapshots[i][j]-(start>-1? snapshots[start][j]: 0);
                    if(dif>0 && dif<k) legal = false;
                }
                if(legal) max = i-start;
            }
        
            return max;
        }
    }

  • 0
    E

    @Minwei It is not O(1)....


  • 0
    M

    @ElayMarco No, It's not, total time is O(N).


Log in to reply
 

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