Rumah > Java > javaTutorial > teks badan

Subrentetan terpanjang tanpa mengulang aksara

Mary-Kate Olsen
Lepaskan: 2024-09-24 06:21:48
asal
704 orang telah melayarinya

Longest substring without repeating characters

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;
    }
}
Salin selepas log masuk

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

sumber:dev.to
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel terbaru oleh pengarang
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan
Tentang kita Penafian Sitemap
Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!