Berilgan matndan belgilari takrorlanmaydigan eng uzun qismni topib, uning uzunligini qaytarish kerak bo’ladi.
Masalan:
Input: s = "abcabcbb" Output: 3 Tushuntirish: The answer is "abc", with the length of 3.
Shartlari:
0 <= s.length <= 5 * 104(matn uzunligi juda katta bo’lishi mumkin).sstring ingliz harflaridan, sonlardan, belgilardan va probeldan tashkil topgan.
Intuitsiya bilan ishlash
Dastlab inson qanday qilib masalani yechishi haqida o’ylab ko’ramiz. Agar string qisqa bo’lsa, inson ko’rib turib, intuitsiya bilan ham topa oladi. Bunda matnning boshidan qaytariladigan belgi kelguncha qarab chiqadi.
abcabcbb
Qaytariladigan harf kelgach, undan avvalgi harflar sonini xotiraga olib qo’yadi. abc uzunligi – 3.
Keyin, ikkinchi harfdan davom ettiradi.
abcabcbb
Yuqoridagi kabi, qaytariladigan harf kelgach, tushirib ketilgan harfdan boshlab qaytarilgan harfgacha bo’lgan harflar sonini xotiraga olib qo’yadi. bca uzunligi – 3.
Shu tariqa protsess davom etadi.
abcabcbb // cab uzunligi - 3
abcabcbb // abc uzunligi - 3
abcabcbb // bc uzunligi - 2
abcabcbb // cb uzunligi - 2
abcabcbb // b uzunligi - 1
abcabcbb // b uzunligi - 1
Xotiraga olingan (yoki yozib qo’yilgan) sonlarning ichida eng kattasi – 3, demak string’dagi belgilari takrorlanmaydigan eng uzun substring uzunligi 3 ga teng ekan.
Yuqoridagi intuitsiyani tahlil qilamiz. Qaytariladigan bir xil harakat bo’lyaptimi? Bo’lyapti – uni siklga olsa bo’ladi. Shuningdek, biz har safar chapdan bitta belgiga surib borib, belgi qaytarilganda tekshirishni to’xtatyapmiz. Ushbu texnikaning nomini sliding window texnikasi deyiladi.
Sliding window
Sliding window texnikasi ko’pincha ro’yhatdagi yonma-yon joylashgan elementlarni tekshirib chiqish uchun ishlatiladi. Masalan, [5, 2, 4, 6, 3, 1] array’dan yig’indisi eng katta son chiqadigan qo’shni juft sonlarni topish kerak bo’lsin. Bu holatda biz shunchaki array’ni tartiblab, ohirgi ikki sonni ololmaymiz. Masalani shartiga ko’ra yonma-yon qo’shni juft sonlarni tekshirib chiqishimiz kerak. Biz sliding window texnikasini qo’llab, elementlarni juft-juft qilib tekshirib chiqamiz:
[5,2] // yig'indisi - 7 [2,4] // 6 [4,6] // 10 [6,3] // 9 [3,1] // 4
Yig’indisi eng katta (10) juft [4,6] ekan. Biz masalani sliding window texnikasi bilan yechdik.
Shuningdek sliding window’ni longest repeated substring uchun ham qo’llash mumkin. Lekin longest repeated substring uchun elegantroq yechim – suffix array yordamida yechishning ham imkoni bor:
* * *
Maqolaning asosiy masalasiga qaytamiz.
Biz masalani sliding window texnikasi bilan yechar ekanmiz, bizga window’ning chap tarafini belgilab olish talab etiladi. Dasturning boshida u 0 ga teng. Shuningdek, eng uzun substring sonini longest o’zgaruvchiga yig’ib boramiz. Bizga barcha substring’larning uzunligini bilish shartmas, faqat eng uzunini qoldirsak kifoya.
const lengthOfLongestSubstring = (str) => {
let left = 0
let longest = 0
}
Elementning qaytarilishini tekshirish uchun Hashtable (yoki Dictionary) ideal yechim, sababi bunda time complexity O(1) ga teng bo’ladi.
const lengthOfLongestSubstring = (str) => {
let left = 0
let longest = 0
counts = {}
}
Endi siklni qo’shamiz. siklning iteratori sliding window’ning o’ng chegarasiga teng bo’ladi. Ma’lum shart bajarilganda o’ng chegarasi ortib boradi.
const lengthOfLongestSubstring = (str) => {
let left = 0
let longest = 0
counts = {}
for (let right = 0; right < str.length; right++) {
}
return longest
}
Sikl ichida counts obyektiga harflarning miqdorini yig’ib boramiz. Harf agar counts ichida yo’q bo’lsa, dastlab unga boshlang’ich 0 qiymat beramiz.
const lengthOfLongestSubstring = (str) => {
let left = 0
let longest = 0
counts = {}
for (let right = 0; right < str.length; right++) {
if (!counts[str[right]]) {
counts[str[right]] = 0
}
counts[str[right]]++
}
return longest
}
Nihoyat window’ni qachon va qaysi holatda surishimiz kerakligini aniqlashtiramiz. biz window’ning chap va o’ng chegarasini left va right o’zgaruvchilari yordamida berishimiz bois, substring – matnni ana shu chegaralar ichidagi qismi hisoblanadi. right oshib borganida substring’ni ko’proq elementlar tashkil eta boshlaydi.
Agar harflar qaytarilsa, left oshib, window chegarasini qisqartiradi. Bu holat matn ohiriga qadar davom etadi. Bu shartlarni ham funksiyaga qo’shamiz.
Menga bir qismi – har bir iteratsiyada arr.some() – qiymati 1 dan katta elementni topish yoqmay turipti. Uni optimizatsiya qilish mumkinmi?
Ha, mumkin ekan. Buning uchun counts ga harflarning uchragan pozitsiyasini yig’ib boramiz. left qiymatini esa counts[char] asosida shakllantiramiz. Tushunishga biroz qiyinroq bo’lishi mumkin, lekin debug bilan amallasa bo’ladi. 😉