[LeetCode] Longest Substring Without Repeating Characters

문제

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

문자열 s가 주어지면 문자를 반복하지 않고 가장 긴 부분 문자열의 길이를 찾습니다.
=> 중복되지 않고 가장 긴 문자열의 길이를 구해라

 

Example

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.

---

풀이

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let answer = '';
  let maxLength = 0;
  
  for(let i = 0; i < s.length; i++) {
    const index = answer.indexOf(s[i]);
    if (index > -1) {
      answer = answer.slice(index + 1);
    }
    answer += s[i];
    
    if (maxLength < answer.length) {
      maxLength = answer.length;
    }
  }
  
  return maxLength;
};

• 생각나는대로 풀었다.
• Runtime: 123ms ~ 160ms
• Memory: 44.1MB ~ 44.3MB

 

다른 사람 풀이

분포율이 제일 높았던 풀이법

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let set = new Set(), res = 0
    for(let i = 0, j = 0; j < s.length; ) {
        if(set.has(s[j])) {
            set.delete(s[i])
            res = Math.max(j - i, res)
            ++i
        }
        else {
            set.add(s[j])
            ++j
        }
    }
    return Math.max(set.size, res)
};

• ES6 Set을 이용한 풀이법. Set에 대해서 다시 한번 리마인드 해야겠다.

 

Runtime이 가장 빨랐던 풀이법

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
   if (!s) return 0;
    if (s.length < 2) return s.length;
    var ls = s[0]; // longest string
    var cs = s[0]; // current string
    for (var i = 1; i < s.length; i++) {
        var index = cs.indexOf(s[i]); // get index of current character in current string
        if (index > -1) { // found the character in current string
            if (cs.length > ls.length) {
                ls = cs; // update longest string
            }
            cs = cs.substring(index + 1,cs.length) + s[i]; // remove the first part of the string which contains repeated character
        } else {
            cs = cs + s[i]; 
        }        
    }
    if (cs.length > ls.length) {
        ls = cs;                
    }
    return ls.length;
};

• 사전에 거를 수 있는 경우의 수를 바로 처리해서 loop의 횟수를 줄였다. 로직 자체는 동일한 것으로 보인다. 앞단에서 케이스를 제거해준 것이 Runtime에서 큰 차이를 줄 수 있다.

---

결론

다양한 풀이법을 습득하고 사전에 거를 수 있는 로직을 추가하자