#masala #leetcode #explanition #med. #pythonadvanced

Quyida leetcode dagi 3 - masala, yechimi tushuntirilgan
(bu mening yechimim va eng optimal yechim bo'lmasligi mumkin)

3. Longest Substring Without Repeating Characters
masala sharti: s satr berilgan (string turidagi o'zgaruvchi), s satr ichidagi birorta belgi takrorlanmagan eng uzun qism satr uzunligini toping.

masala yechimi:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left_position = 0
        substring_finding = set()
        substring_length = 0
        for right_position in range(len(s)):
            while s[right_position] in substring_finding:
                substring_finding.remove(s[left_position])
                left_position += 1
            substring_finding.add(s[right_position])
            substring_length = max(substring_length, len(substring_finding))
        return substring_length

masala tahlili:
Bir qarashda oddiy misoldek tuyulishi mumkin, va aytishingiz mumkin oddiy ichma-ich for orqali yechish mumkin deb, lekin bu holda vaqt murakkabligi oshib ketadi. Dastur bajarilishiga ketgan vaqt meyoridan oshib testdan o'ta olmaydi.
Yuqoridagi yechim esa vaqt meyori talablariga ham javob beradi.

Yechimning g'oyasi:
Tasavvur qilaylik biz izlagan qism satr berilgan s satrning qaysidir qismida joylashgan va u albatta s satrning qaysidir pozitsiyasidan (left_position) boshlanib qaysidir positsiyasida (right_position) tugaydi. Biz bu o'zgaruvchilarga boshlang'ich qiymat nolni o'zlashtiramiz (biz izlashni s satrning boshidan boshlaganimiz uchun boshlang'ich left_position ga nol qiymat beramiz),

shuningdek, bizga pustoy s satr berilishi mumkinligini ham inobatga olib substring_length ga ham nol qiymat bervolamiz.

substring_finding ni takrorlanuvchi elementga ega bo'lmagan tur set() deb e'lon qilamiz (biz izlagan qism satrni o'zi mavjud bo'lmasligini ham inobatga olgan holda u ham boshlanishida bo'sh bo'ladi) .

bittalik for sikli orqali biz berilgan s satrdan boshidan boshlab bittadan harfni substring_finding ga qo'shib boramiz,

lekin qachonki biz qo'shmoqchi bo'lgan belgi substring_finding tarkibida bor bo'lsa (while siklining ichi) (bu biz qidirayotgan qism satr talabiga mos kelmaydi chunki biz tarkibida takrorlanuvchi belgi bo'lmagan qism satr qidiryapmiz) substring_finding tarkibidagi shu belgi o'chib ketmaguncha substring_finding ning birinchi elementini (s satrning left_position pozitsiyasida turgan elementi s[left_position] ni) o'chiramiz va left_position qiymatini keyingi belgi pozitsiyasiga o'zgartirib qo'yamiz (left_position +=1).

Shunday qilib for siklining har bir siklida hosil bo'lgan qism satr ( substring_finding ) ning uzunligini shu vaqtgacha topilgan eng uzun uzunlik bilan solishtirib turamiz va uzunrog'i topilsa yangi uzunlikni o'zlashtiramiz
(
substring_length = max( substring_length, len( substring_finding)
)

Boshlovchilar uchun yopiq kanalimiz:
https://t.me/+4-HzPYPUWWw3NDEy

Python bo'yicha ozroq tajriba ega bo'lganlar uchun yopiq kanal:
https://t.me/+G8Ao2nlAzBQ0ZGIy

Leetcode masalalari bo'yicha:
https://t.me/+x2ag7zS70DQyMjJi

https://t.me/simplypythonuz