Skip to content

Latest commit

ย 

History

History
29 lines (27 loc) ยท 1.23 KB

step1.md

File metadata and controls

29 lines (27 loc) ยท 1.23 KB

step1 ไฝ•ใ‚‚่ฆ‹ใšใซ่งฃใ

ๆ–‡ๅญ—ใ‚’ๅ‰ใ‹ใ‚‰ไธ€ใคใšใคใฟใฆใ„ใฃใฆใ€้–‹ๅง‹ๆ™‚็‚นใ‹ใ‚‰ไปŠ่ฆ‹ใฆใ‚‹ใจใ“ใ‚ใพใงใฎๆ–‡ๅญ—ๅˆ—ใŒใ™ในใฆใƒฆใƒ‹ใƒผใ‚ฏใชๆ–‡ๅญ—ใ‚’ๅซใ‚€ๆ–‡ๅญ—ๅˆ—ใ‹ใฉใ†ใ‹ใ‚’ใƒใ‚งใƒƒใ‚ฏใ—ใŸใ„ใ€‚ ่ฆ‹ใŸๆ–‡ๅญ—ใ‚’็ฎก็†ใ™ใ‚ŒใฐไปŠ่ฆ‹ใฆใ„ใ‚‹ๆ–‡ๅญ—ใŒๆ—ขใซ่ฆ‹ใŸใ“ใจใ‚ใ‚‹ใ‹ใฉใ†ใ‹ใŒใ‚ใ‹ใ‚‹ใ€‚ ๆ—ขใซ่ฆ‹ใŸๆ–‡ๅญ—ใŒใ‚ใ‚‹ใจใใ€ใ“ใฎๆ–‡ๅญ—ใ‚’ๅซใ‚€ๅ ดๅˆใฉใ“ใพใงๅพŒใ‚ใงใ‚ใ‚Œใฐๅ•้กŒใชใ„ใ‹ใ‚’็Ÿฅใ‚ŠใŸใ„ใ€‚ ไพ‹ใˆใฐabcdec....ใจใ„ใ†ๆ–‡ๅญ—ๅˆ—ใŒใ‚ใ‚‹ๆ™‚ใซใ€ไบŒๅ›ž็›ฎใฎcใŒๆฅใŸๆ™‚ใซdecใฏๅ•้กŒใชใ„ใฎใงๆฌกใ‚’่ฆ‹ใซ่กŒใใ€ใจใ„ใ†ใ“ใจใ‚’ใ—ใŸใ„ใ€‚ ใใ‚Œใ‚’ๅฎŸ็พใ™ใ‚‹ใซใฏใ€ไปŠ่ฆ‹ใฆใ„ใ‚‹ๆ–‡ๅญ—ใŒใชใใชใ‚‹ใพใง้–‹ๅง‹ๆ™‚็‚นใ‚’้€ฒใ‚ใ‚Œใฐใ‚ˆใ„ใ€‚ ใ“ใ†ใ„ใ†ๆ„Ÿใ˜ใฎ็™บๆƒณใงใ„ใ‘ใ‚‹ใฏใšใ€‚

ๆ™‚้–“่จˆ็ฎ—้‡ใฏO(N)ใง็ฉบ้–“่จˆ็ฎ—้‡ใ‚‚O(N) Nใฎๆœ€ๅคงๅ€คใฏ5 * 10^4ใชใฎใง1็ง’ไปฅๅ†…ใซ็ต‚ใ‚ใ‚‹ใ€‚

# @param {String} str
# @return {Integer}
def length_of_longest_substring(str)
    chars_in_substr = Set.new
    l = 0
    res = 0
    str.size.times do |r|
        while chars_in_substr.include?(str[r])
            chars_in_substr.delete(str[l])
            l += 1
        end
        chars_in_substr << str[r]
        res = [res, r - l + 1].max
    end
    res
end