Harflari takrorlanmagan qism
Berilgan string ichida hech bir belgi takrorlanmaydigan eng uzun uzluksiz qismni topish kerak.
Kirish: "abcabcbb"
Chiqish: 3 ("abc" — birinchi uchta belgi)
Kirish: "bbbbb"
Chiqish: 1 ("b" — faqat bitta belgi)
Kirish: "pwwkew"
Chiqish: 3 ("wke" — o'rtadagi uch belgi)
Bu masala amaliy dasturlardan kelib chiqqan. Fayl tizimida noyob nomlar ketma-ketligini tekshirish, tarmoq protokolida noyob kalit uzunligini aniqlash, matn tahlilida takrorlanmaydigan qismlarni ajratish — bularning barchasi shu masalaning turli ko'rinishlari.
Nima sababdan bu masala murakkab?
Bir qarashda oddiy ko'rinadi: "belgilarni ko'r, takroriy chiqsa to'xta". Lekin masala "eng uzun qism"ni talab qiladi. Demak, birinchi topilgan noyob qism bilan cheklanib bo'lmaydi — barcha mumkin bo'lgan uzluksiz qismlar ichida eng uzunini topish kerak.
Yana bir muammo: takroriy belgi topilganda, qidiruvni qaerdan davom ettirishni aniqlash. Masalan, "abcab" stringida i=3-da 'a' takrori topildi. Endi i=1-dan qayta boshlaydimi? Yoki i=4-dan davom etadimi? Bu savolga noto'g'ri javob noto'g'ri natijaga olib keladi.
Sodda yondashuv: barcha qismlarni tekshirish
Birinchi g'oya — har bir pozitsiyadan boshlab barcha mumkin bo'lgan qismlarni ko'rib chiqish:
FUNCTION sodda_yondashuv(s):
maksimal = 0
i = 0
WHILE i < s.length:
j = i
ko'rilgan = bo'sh to'plam
WHILE j < s.length:
IF s[j] ko'rilganda mavjud:
BREAK // takror topildi
ko'rilganga s[j] qo'sh
j = j + 1
maksimal = max(maksimal, j - i)
i = i + 1
RETURN maksimal
Bu yondashuv to'g'ri ishlaydi. Lekin har bir pozitsiya uchun ichki tsikl qaytadan boshlanadi. Jami ish O(n²) — n ta pozitsiya, har birida ko'pi bilan n ta solishtirish.
Kichik string uchun bu yetarli. Lekin million belgili matn uchun trillion amalga yaqin ish kerak bo'ladi — bu hech qanday amaliy tizim uchun mos emas.
Siljuvchi oyna: har bir belgini bir marta ko'rish
Samarali yondashuv — siljuvchi oyna (sliding window). Asosiy g'oya quyidagicha: oynaning o'ng chegarasi doimo oldinga yuradi. Takroriy belgi topilganda, o'ng chegarani to'xtatmasdan, chap chegarani takroriy belgi o'tib ketgunga qadar oldinga surish kerak.
Bunda chap chegarani birinchi 'a' o'tib ketgunga qadar siljitamiz:
Endi takror yo'q, o'ng chegara yana oldinga yuradi.
Shu mantiqqа asoslanib, har bir belgini faqat bir marta ko'rish mumkin bo'ladi.
Lug'at bilan siljuvchi oyna
Har bir belgining oyna ichidagi oxirgi pozitsiyasini lug'atda saqlash mumkin. Takroriy belgi topilganda, uning oxirgi uchragan joyi ma'lum bo'ladi va chap chegara to'g'ridan-to'g'ri shu joydan keyingi pozitsiyaga o'tkaziladi.
FUNCTION siljuvchi_oyna(s):
oxirgi_pozitsiya = bo'sh lug'at // belgi → oxirgi indeksi
maksimal = 0
l = 0
r = 0
WHILE r < s.length:
belgi = s[r]
IF belgi lug'atda mavjud AND lug'at[belgi] >= l:
// belgi oyna ichida takror uchradi
l = lug'at[belgi] + 1 // chap chegarani siljit
lug'at[belgi] = r // oxirgi pozitsiyani yangilash
maksimal = max(maksimal, r - l + 1)
r = r + 1
RETURN maksimal
Muhim shart: lug'at[belgi] >= l. Bu shart nima uchun kerak? Chunki lug'atda hali oynadan chiqib ketgan belgilarning eski pozitsiyalari saqlanib qolgan bo'lishi mumkin. Masalan, "abba" stringida 'a' birinchi indeksi 0da saqlangan. Keyin oyna "bb" ga yetganda 'a' allaqachon oynadan chiqib ketgan. Agar 'a' yana uchrasa va lug'at['a'] = 0 bo'lsa, bu holda l = 0 + 1 = 1 qilish noto'g'ri — l allaqachon 2 yoki 3da bo'lishi mumkin. Shuning uchun lug'at[belgi] >= l ekanligini tekshirish kerak.
Dry run: bosqichma-bosqich kuzatish
"abcabcbb" ustida:
lug'at = {}, l = 0, maksimal = 0
r=0, belgi='a': lug'atda yo'q → lug'at={'a':0}, oyna=[a], uzunlik=1, maksimal=1
r=1, belgi='b': lug'atda yo'q → lug'at={'a':0,'b':1}, oyna=[ab], uzunlik=2, maksimal=2
r=2, belgi='c': lug'atda yo'q → lug'at={'a':0,'b':1,'c':2}, oyna=[abc], uzunlik=3, maksimal=3
r=3, belgi='a': lug'atda bor, lug'at['a']=0 >= l=0
→ l = 0 + 1 = 1
→ lug'at['a'] = 3
→ oyna=[bca], uzunlik=3, maksimal=3
r=4, belgi='b': lug'atda bor, lug'at['b']=1 >= l=1
→ l = 1 + 1 = 2
→ lug'at['b'] = 4
→ oyna=[cab], uzunlik=3, maksimal=3
r=5, belgi='c': lug'atda bor, lug'at['c']=2 >= l=2
→ l = 2 + 1 = 3
→ lug'at['c'] = 5
→ oyna=[abc], uzunlik=3, maksimal=3
r=6, belgi='b': lug'atda bor, lug'at['b']=4 >= l=3
→ l = 4 + 1 = 5
→ lug'at['b'] = 6
→ oyna=[cb], uzunlik=2, maksimal=3
r=7, belgi='b': lug'atda bor, lug'at['b']=6 >= l=5
→ l = 6 + 1 = 7
→ lug'at['b'] = 7
→ oyna=[b], uzunlik=1, maksimal=3
r=8: tsikl tugadi.
RETURN 3
Natija: 3. Bu "abc" qismi — birinchi uch belgi.
Lug'at o'rniga to'plam ishlatish
Alternativ yondashuv — lug'at o'rniga to'plam (set) ishlatish. To'plamda oyna ichidagi belgilar saqlanadi. Takroriy belgi topilganda, chap chegara shu belgi to'plamdan ketgunga qadar birer qadam siljitiladi.
FUNCTION to'plam_bilan(s):
to'plam = bo'sh to'plam
maksimal = 0
l = 0
r = 0
WHILE r < s.length:
WHILE s[r] to'plamda mavjud:
to'plamdan s[l] olib tashlash
l = l + 1
to'plamga s[r] qo'sh
maksimal = max(maksimal, r - l + 1)
r = r + 1
RETURN maksimal
Bu yondashuv to'g'ri ishlaydi, lekin takroriy belgi topilganda chap chegarani birer qadam siljitadi. Lug'at yondashuvida esa to'g'ridan-to'g'ri to'g'ri joyga sakrash mumkin — shu sababli lug'at yondashuvida amalda kamroq qadam bo'lishi mumkin. Vaqt murakkabligi ikkisida ham O(n), lekin lug'at yondashuvida ichki tsikl yo'q.
Chegara holatlari
Bo'sh string: Tsikl boshlanmaydi, maksimal = 0 qaytariladi — to'g'ri.
Barcha belgilar bir xil ("bbbbb"):
- r=0: 'b' yo'q → oyna=[b], maksimal=1
- r=1: 'b' bor → l=1, oyna=[b], maksimal=1
- ... har safar oyna bitta belgidan iborat
- Natija: 1
Hamma belgi noyob ("abcde"):
- Hech qachon chap chegara siljimaydi
- r=4 da oyna=[abcde], maksimal=5
- Natija: 5
Ikkita belgi ("au"):
- r=0: 'a' yo'q → oyna=[a], maksimal=1
- r=1: 'u' yo'q → oyna=[au], maksimal=2
- Natija: 2
Note
lug'at[belgi] >= l shartini e'tibordan qoldirmaslik kerak. Bu shart bo'lmasa, allaqachon oynadan chiqib ketgan belgilarning eski pozitsiyalari chap chegarani noto'g'ri joyga siljitadi va natija yolg'on bo'ladi. Masalan, "abba" uchun to'g'ri javob 2, lekin bu shart bo'lmasa 1 chiqishi mumkin.
Vaqt va xotira murakkabligi
| Yondashuv | Vaqt murakkabligi | Xotira murakkabligi |
|---|---|---|
| Barcha qismlarni tekshirish | O(n²) | O(k) |
| Siljuvchi oyna + lug'at | O(n) | O(k) |
| Siljuvchi oyna + to'plam | O(n) | O(k) |
k — noyob belgilar soni. Faqat kichik ingliz harflari bo'lsa k ≤ 26, shuning uchun xotira murakkabligi O(1) hisoblanadi.
Nima uchun siljuvchi oyna O(n)?
Har bir belgi oynaga bir marta kiradi va bir marta chiqadi. r ko'rsatkichi 0 dan n-1 gacha — n qadam. l ko'rsatkichi ham 0 dan ko'pi bilan n gacha siljiydi — n qadam. Jami 2n qadam, ya'ni O(n).
Sodda yondashuvda esa har bir pozitsiya uchun ichki tsikl qaytadan boshlanadi. n ta pozitsiya, har birida ko'pi bilan n ta qadam — jami O(n²).
Bu masalaning o'rni
Bu masala siljuvchi oyna texnikasining klassik namunasi. Oyna qachon kengayishi, qachon torayishini tushunish — boshqa ko'plab masalalar uchun ham zarur fikrlash tarzini shakllantiradi:
- berilgan shartni bajaradigan eng qisqa substring;
- barcha belgilar kamida bir marta uchraydigan eng kichik oyna;
- ma'lum sondagi turli belgini o'z ichiga olgan eng uzun qism.
Bularning hammasi "o'zgaruvchan o'lchamli siljuvchi oyna" sinfiga kiradi va bir xil asosiy mantiqqа asoslanadi.