3. Longest Substring Without Repeating Characters

안녕 오랜만에 돌아온 리트코드~

문제 설명

문자열 s가 주어졌을 때, 반복되는 문자가 없는 가장 긴 substring의 길이를 출력하시오 .

출력예시

접근 방법

첫번째 시도

해시 테이블 ~~
하다가 문제를 잘못 읽었다. 그냥 앞에서부터 비교함,, 문제를 자세히 읽자

두번째 시도

일단은 이중 for문을 이용하여 O(n2)로 완전 탐색하기

소스코드

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int result=0;
        vector<int> answer;
        int alphabet[200]={0};
        
        if(s.length()<=1){
            result = s.length();   
        }
        else{
            for(int i=0; i<s.length(); i++){
                int alphabet[200]={0};
                int ans=0;
                for(int j=i; j<s.length(); j++){
                    if(alphabet[s[j]]==0){
                        alphabet[s[j]]++;
                        ans++;
                        if(j==s.length()-1) answer.push_back(ans);
                        
                    }else {
                        answer.push_back(ans);
                        break;
                    }
                }

            }    

            result = *max_element(answer.begin(),answer.end());
        }
        return result;
    }
};

돌아보기

완전 탐색 말고도 map을 이용하여 문자와 해당 인덱스값을 같이 저장한다면 더 효율적인 시간복잡도로 구현 가능하다. 사실 아직 이해 못함 ㅠ 다시 체크해보기