[LeetCode] 3 - Longest Substring Without Repeating Characters

문제

• 링크: https://leetcode.com/problems/longest-substring-without-repeating-characters
• 난이도: Medium
• 태그: 해시 테이블, 문자열, 슬라이딩 윈도우
• 결과: Time: 6 ms (67.18%), Space: 11.88 MB (56.28%)

풀이

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        unordered_map<char, int> m; // 현재 윈도우 내에 있는 문자 - 인덱스
        int maxLen = 0;
        int l = 0;
        for (int r = 0; r < n; ++r)
        {
            if (m.contains(s[r])) // 중복된 문자를 찾은 경우
            {
                l = max(m[s[r]] + 1, l); // 해당 문자가 l보다 뒤에 있다면 l을 거기로 옮김
            }

            m[s[r]] = r; // s[r]의 위치 업데이트

            maxLen = max(maxLen, r - l + 1);
        }

        return maxLen;
    }
};

처음에는 비효율적으로 풀었다가, AI의 도움을 받아서 투 포인터 기반 풀이로 수정했다.

배운 점과 후기

음, 투 포인터라고 해서 항상 while (l < r)을 떠올리면 안되겠다.

이 포스트는 달레 스터디(7주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.