WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Leetcode 3. Longest Substring Without Repeating Characters

Berilgan matndan belgilari takrorlanmaydigan eng uzun qismni topib, uning uzunligini qaytariş kerak böladi.

Masalan:

Input: s = "abcabcbb" Output: 3 Tuşuntiriş: The answer is "abc", with the length of 3.

Şartlari:

  • 0 &lt;= s.length &lt;= 5 * 10<sup>4</sup> (matn uzunligi juda katta bölişi mumkin).
  • s string ingliz harflaridan, sonlardan, belgilardan va probeldan taşkil topgan.

Intuitsiya bilan işlaş

Dastlab inson qanday qilib masalani yeçişi haqida öylab köramiz. Agar string qisqa bölsa, inson körib turib, intuitsiya bilan ham topa oladi. Bunda matnning boşidan qaytariladigan belgi kelgunça qarab çiqadi.

abcabcbb

Qaytariladigan harf kelgaç, undan avvalgi harflar sonini xotiraga olib qöyadi. abc uzunligi - 3.

Keyin, ikkinçi harfdan davom ettiradi.

abcabcbb

Yuqoridagi kabi, qaytariladigan harf kelgaç, tuşirib ketilgan harfdan boşlab qaytarilgan harfgaça bölgan harflar sonini xotiraga olib qöyadi. bca uzunligi - 3.

Şu 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 qöyilgan) sonlarning içida eng kattasi - 3, demak strinğdagi belgilari takrorlanmaydigan eng uzun substring uzunligi 3 ga teng ekan.

Yuqoridagi intuitsiyani tahlil qilamiz. Qaytariladigan bir xil harakat bölyaptimi? Bölyapti - uni siklga olsa böladi. Şuningdek, biz har safar çapdan bitta belgiga surib borib, belgi qaytarilganda tekşirişni töxtatyapmiz. Uşbu texnikaning nomini sliding window texnikasi deyiladi.

Sliding window

Sliding window texnikasi köpinça röyhatdagi yonma-yon joylaşgan elementlarni tekşirib çiqiş uçun işlatiladi. Masalan, [5, 2, 4, 6, 3, 1] array'dan yiğindisi eng katta son çiqadigan qöşni juft sonlarni topiş kerak bölsin. Bu holatda biz şunçaki array'ni tartiblab, ohirgi ikki sonni ololmaymiz. Masalani şartiga köra yonma-yon qöşni juft sonlarni tekşirib çiqişimiz kerak. Biz sliding window texnikasini qöllab, elementlarni juft-juft qilib tekşirib çiqamiz:

[5,2] // yiğindisi - 7 [2,4] // 6 [4,6] // 10 [6,3] // 9 [3,1] // 4

Yiğindisi eng katta (10) juft [4,6] ekan. Biz masalani sliding window texnikasi bilan yeçdik.

Şuningdek sliding window'ni longest repeated substring uçun ham qöllaş mumkin. Lekin longest repeated substring uçun elegantroq yeçim - suffix array yordamida yeçişning ham imkoni bor:

/2020/12/12/suffix-array-va-matnni-suffix-arrayda-qayta-işlaş/


Maqolaning asosiy masalasiga qaytamiz.

Biz masalani sliding window texnikasi bilan yeçar ekanmiz, bizga window'ning çap tarafini belgilab oliş talab etiladi. Dasturning boşida u 0 ga teng. Şuningdek, eng uzun substring sonini longest özgaruvçiga yiğib boramiz. Bizga barça substrinğlarning uzunligini biliş şartmas, faqat eng uzunini qoldirsak kifoya.

const lengthOfLongestSubstring = (str) => {
  let left = 0
  let longest = 0
}

Elementning qaytarilişini tekşiriş uçun Hashtable (yoki Dictionary) ideal yeçim, sababi bunda time complexity O(1) ga teng böladi.

const lengthOfLongestSubstring = (str) => {
  let left = 0
  let longest = 0
  counts = {}
}

Endi siklni qöşamiz. siklning iteratori sliding window'ning öng çegarasiga teng böladi. Ma'lum şart bajarilganda öng çegarasi ortib boradi.

const lengthOfLongestSubstring = (str) => {
  let left = 0
  let longest = 0
  counts = {}

  for (let right = 0; right < str.length; right++) {
  
  }

  return longest
}

Sikl içida counts obyektiga harflarning miqdorini yiğib boramiz. Harf agar counts içida yöq bölsa, dastlab unga boşlanğiç 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 qaçon va qaysi holatda surişimiz kerakligini aniqlaştiramiz. biz window'ning çap va öng çegarasini left va right özgaruvçilari yordamida berişimiz bois, substring - matnni ana şu çegaralar içidagi qismi hisoblanadi. right oşib borganida substrinğni köproq elementlar taşkil eta boşlaydi.

Agar harflar qaytarilsa, left oşib, window çegarasini qisqartiradi. Bu holat matn ohiriga qadar davom etadi. Bu şartlarni ham funksiyaga qöşamiz.

Menga bir qismi - har bir iteratsiyada arr.some() - qiymati 1 dan katta elementni topiş yoqmay turipti. Uni optimizatsiya qiliş mumkinmi?

Ha, mumkin ekan. Buning uçun counts ga harflarning uçragan pozitsiyasini yiğib boramiz. left qiymatini esa counts[char] asosida şakllantiramiz. Tuşunişga biroz qiyinroq bölişi mumkin, lekin debug bilan amallasa böladi. ;)