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!