Subrentetan terpanjang tanpa mengulang aksara

Masalah

Pendekatan brute force akan melibatkan mencipta semua subrentetan yang mungkin bagi rentetan yang diberikan dan mengetahui yang mana subrentetan terpanjang tanpa aksara berulang. Ini akan membawa kepada TC:O(n^2)

Pendekatan optimum:
TC : O(n)
SC : O(256), untuk menggunakan int[] saiz 256

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int hash[] = new int[256];// size of all the ascii characters
        Arrays.fill(hash,-1); // -1 to indicate these indexes don't have any character visited already
        int left =0,right =0;
        int max = 0;
        while(right<s.length()){
            char  c = s.charAt(right);
            if(hash[c]!=-1){// means the character has been seen in the past
                if(hash[c]>=left){// if the index of the character seen in the past is after the left pointer, then left pointer should be updated, to avoid duplicate in the window of substring
                    left  = hash[c] + 1;// has to be 1 index after the index of last seen duplicate character
                }
            }
            max = Integer.max(max, right-left+1);// keep track of mas window substring
            hash[c]  = right;// update the character last seen index in hash
            right++;
        }
        return max;
    }
}

Atas ialah kandungan terperinci Subrentetan terpanjang tanpa mengulang aksara. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!