Longest Substring Without Repeating Characters

problem

주어진 문장에서 중복없이 가장 긴 부분 문자열을 찾는 문제입니다.

solution

//problem no: 3 
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        string sub = "";
        int start = 0;
        int m = 0;
        
        for(int i=0;i<s.size();i++){
            for(int j=start;j<sub.size();j++){
                if(s[i] == sub[j]){
                    m = max(m, i-start);
                    start = j+1;
                }        
            }
            sub.push_back(s[i]);
        }
        if(m < s.size()-start){
            m = s.size() - start;
        }
        return m;
    }  
};

How I think

제가 생각한 방법은 substring을 만들면서 한개씩 검사하는 문제입니다. 즉 중복이 없어야하므로, 중복이 아닌 문자는 그대로 들어가고 중복이 있으면 문자열이 분할된다는 것입니다. (max도 중복이 있을 때, 갱신된다.)

pwwke 같은경우, pw가 들어가고 w를 넣을 때 w가 이미 존재하므로, pw / w 가 되는 것입니다. 이후에 ke는 중복이 없으므로 그대로 들어가 wke가 완성됩니다.

후기

메모리는 적게 썼지만, 속도가 좀 느렸습니다.
'중복이 없게 한다'를 구현하는데 substring을 모두 순회해서 그런 것 같습니다.

map이나 배열을 써서 체크했으면 더 좋았을 것 같습니다. 난이도가 미디움이라 그런지 아직은 벅찬 느낌이 있습니다. 힘내자