Longest Substring Without Repeating Characters (Medium)

문제

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.
 

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

---

풀이

문자열 하나하나 비교하면서 중복되지 않은 문자가 나올 때 까지 탐색하기.

 

이중 for문으로 기준 문자열과 비교 대상 문자열을 비교

 for (i = 0; i < s.length; i++) {
 	for (j = i; j < s.length; j++) {

 

문자가 다르면 cnt를 1씩 늘리고 같을 떼 break !

이 후에 처음 선언 했던 maxcnt = 1 변수에 Math.max 함수를 이용해 cnt와 maxcnt 중 더 큰 값으로 재 할당.

 

간과한 점:

단순히 문자열만 비교하면 기준 문자열 이후에 오는 중복된 문자열을 무시하게 됨.

"abcba" 같은 경우 b가 2번 나왔기 때문에 조건문을 빠져나와야 하는데, 기준 문자 'a' 만 비교하기 때문에 마지막 a까지 탐색을 해야 탈출을 함.

 

해결책 :

Set 함수를 쓴다.

var seen = new Set();

로 초기화 하고 문자열을 비교 할때마다 seen에 문자를 넣고 중복이 있는지를 확인.

---

답안

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    var maxcnt = 1;
    
    if (s === ' ') return 1;
    if (s === '') return 0;

    for (i = 0; i < s.length; i++) {
        var seen = new Set();   // Set : 중복되지 않은 유일한 값들의 집합을 관리하는 객체
        var cnt = 0;

        for (j = i; j < s.length; j++) {
            if (!seen.has(s[j])) {  // Set에 없으면
                seen.add(s[j]);     // 넣어라
                ++cnt;
            }
            else {
                break;
            }
        }
        maxcnt = Math.max(maxcnt, cnt);
    }
    return maxcnt;
};