(Leet Code c++)Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

 

Given a string s, find the length of the longest substring without repeating characters.

 

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

 

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

 

Example 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.

 

Example 4:

Input: s = "" Output: 0

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

 

브루트 포스 알고리즘.

주어진 문자열에서 반복되는 문자없이 가장 긴 문자열의 길이를 리턴해야 한다.

그러기 위해서는 이중 for문을 사용.

 

i번째 문자부터 시작해 s 끝까지 탐색을 하면서 반복되는 문자가 있는지 check 벡터를 이용해 확인한다.

만약 중복되는 문자가 있다면 안쪽에 있는 j for문은 break,

중복되지 않는다면 문자 수를 카운팅하면서 check 벡터의 j 문자를 true로 바꿔준다.

 

바깥쪽 for문의 끝에는 ans와 sum을 비교해 가장 긴 문자열의 길이를 ans에 저장하면 된다.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        
        for(int i = 0; i < s.size(); i++){
            vector<bool> check(200, false);
            int sum = 0;
            
            for(int j = i; j < s.size(); j++){
                if(!check[s[j]]){
                    check[s[j]] = true;
                    sum++;
                }
                else{
                    break;
                }
            }
            ans = ans < sum ? sum : ans;
        }
        
        return ans;
    }
};