All Articles

Longest Substring Without Repeating Characters

substring ๊ด€๋ จํ•œ ๋ฌธ์ œ๋Š” brute force๋กœ ํ’€๋ฉด (i, j) ๊ตฌ๊ฐ„ (O(n^2))์— ๋‹ค์‹œ ๊ฐ ๋ฌธ์ œ๋ณ„๋กœ ์กฐ๊ฑด์„ ๊ฒ€์‚ฌํ•˜๋Š” ๋น„์šฉ์ด ๊ณฑํ•ด์ง€๊ฒŒ ๋˜๋Š”๋ฐ (๋ณดํ†ต input string์˜ ๊ธ€์ž ์ˆ˜์— ๋น„๋ก€), ์—ฌ๊ธฐ์„œ ๋น ๋ฅด๊ฒŒ ๋Œ๋ฆฌ๊ณ  ์‹ถ์„ ๋•Œ๋Š” ์‹คํ–‰๋˜๋Š” (i, j)์˜ ๊ฐœ์ˆ˜๋ฅผ ์ค„์ด๋Š” ์ˆ˜ ๋ฐ–์— ์—†๋‹ค. substring์„ ์ฐพ๋Š” ๋ฌธ์ œ์—์„œ ๋ถ€๋ถ„ ์ผ์น˜ ํ…Œ์ด๋ธ”์„ ๋งŒ๋“ค์–ด๋†“์œผ๋ฉด ๊ธฐ์กด์— ์ฐพ์•„๋†“์€ substring ์ •๋ณด๋ฅผ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ๋“ฏ์ด ์ด ๋ฌธ์ œ์—์„œ๋„ ์•ž์—์„œ ์“ฐ๋˜ ์ •๋ณด๋ฅผ ๊ทธ๋Œ€๋กœ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:
        longest = 0
        d = {}
        start = 0
        
        for end in range(0, len(s)):
            c = s[end]
            if d.get(c) is None or d.get(c) < start:
                d[c] = end
                longest = max(longest, end-start +1)
            else: # d.get(c) >= start
                start = d.get(c) + 1
                d[c] = end

        return longest

๋ฃจํ”„๊ฐ€ ๋„๋Š” ๋‚ด๋‚ด ์ง€์ผœ์ ธ์•ผ ํ•˜๋Š” ๊ฒƒ์€ ๊ตฌ๊ฐ„ [start, end] ์‚ฌ์ด์— repeating character๊ฐ€ ํ•˜๋‚˜๋„ ์กด์žฌํ•˜๋ฉด ์•ˆ๋œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ์ƒˆ๋กœ ๋งŒ๋‚œ character๊ฐ€ ๋”•ํŠธ์— ์—†๊ฑฐ๋‚˜, start ์ด์ „์— ๋‚˜ํƒ€๋‚ฌ์—ˆ์œผ๋ฉด [start, end] ๊ตฌ๊ฐ„์ด ๊ธธ์–ด์ง€๋Š” ๊ฒƒ์ด๊ณ  start, end ์‚ฌ์ด์— ์žˆ์—ˆ์œผ๋ฉด start๋ฅผ ๋’ค๋กœ ๋ฏธ๋ค„์„œ ์ƒˆ ๊ตฌ๊ฐ„์„ ๋งŒ๋“ ๋‹ค.

Published Mar 29, 2020

If I keep marking the dots, someday they will ๐Ÿ”—๐Ÿ”—