문제

주어진 문자열에서 반복되지 않은 가장 긴 문자열의 길이를 구하는 함수를 작성하세요.

[예제 1]
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

[예제 2]
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

[예제 3]
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

풀이

1. 최대 길이를 저장할 변수 max_length와 반복된 문자열을 저장할 배열 arr 초기화
2. for문으로 문자열을 한 글자씩 반복
   2-1. arr에 없는 문자라면 추가
   2-2. arr에 있는 문자라면 겹치는 문자열까지를 잘라내고, arr에 새로 문자 추가
   2-3. max_length가 현재 arr 길이보다 짧다면, max_length를 현재 arr 길이로 업데이트

• 전체 문자열에서 지금까지 있었던 최대길이를 구해야 하므로 max_length가 arr와 별개로 존재해야 한다.

[예제1]
주어진 문자열: abcabcbb
a
arr = ['a'], max_length = 1
ab
arr = ['a', 'b'], max_length = 2
abc
arr = ['a', 'b', 'c'], max_length = 3
abca
arr = ['a'], max_length = 3
abcab
arr = ['a', 'b'], max_length = 3
abcabc
arr = ['a', 'b', 'c'], max_length = 3
abcabcb
arr = ['b'], max_length = 3
abcabcbb
arr = ['b'], max_length = 3

[예제2]
주어진 문자열: bbbbb
b ~ bbbbb
arr = ['b'], max_length = 1

[예제3]
주어진 문자열: pwwkew
p
arr = ['p'], max_length = 1
pw
arr = ['p', 'w'], max_length = 2
pww
arr = ['w'], max_length = 2
pwwk
arr = ['w', 'k'], max_length = 2
pwwke
arr = ['w', 'k', 'e'], max_length = 3
pwwkew
arr = ['k', 'e', 'w'], max_length = 3

• Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_length = 0
        arr = []

        for char in s:
            if char not in arr:
                arr.append(char)
            else:
                arr = arr[arr.index(char) + 1:]
                arr.append(char)
            if max_length < len(arr):
                max_length = len(arr)

        return max_length

• C++

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        int max_length = 0;
        std::unordered_map<char, int> charIndexMap;
        int start = 0;

        for (int i = 0; i < s.length(); ++i) {
            char currentChar = s[i];
            if (charIndexMap.find(currentChar) != charIndexMap.end() && charIndexMap[currentChar] >= start) {
                start = charIndexMap[currentChar] + 1;
            }
            charIndexMap[currentChar] = i;
            max_length = std::max(max_length, i - start + 1);
        }

        return max_length;
    }
};