Leet Code - Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters - LeetCode

 

나의 풀이

 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        Map<Character, Integer> map = new HashMap<>();
        int maxLen = 0;
        int curLen = 0;
        for (int i = 0; i < len; i++) {
            if (map.containsKey(s.charAt(i)) && curLen >= i - map.get(s.charAt(i))) {
                curLen = i - map.get(s.charAt(i));
            } else {
                curLen++; 
            }
            map.put(s.charAt(i), i);
            maxLen = Math.max(maxLen, curLen);
        }
        return maxLen;
    }
}

 

 

 

떠올린 방식

1. brute force

- time complexity : O(n^3)

- logic : 모든 substring을 만든 다음에 중복 없는 가장 긴 단어의 길이를 구한다

 

2. hashmap 이용

- time complexity : O(n)

- logic : map에 해당 캐릭터가 이전까지 몇개 나왔었는지를 체크하다가 해당 map에 이미 포함되어 있는 문자를 발견하면 이전의 개수를 초기화시키는 방식

 

 

 

결과

---

다른 사람의 풀이

 

1. 솔루션

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> chars = new HashMap();

        int left = 0;
        int right = 0;

        int res = 0;
        while (right < s.length()) {
            char r = s.charAt(right);
            chars.put(r, chars.getOrDefault(r,0) + 1);
            
            while (chars.get(r) > 1) {
                char l = s.charAt(left);
                chars.put(l, chars.get(l) - 1);
                left++;
            }

            res = Math.max(res, right - left + 1);

            right++;
        }
        return res;
    }
}

• algorithm : sliding window
• time complexity : O(2n) = O(n)
• space complexity : O(min(m,n))
•  

 

2. 솔루션 최적화

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

• time complexity : O(n)
• space complexity : O(min(m,n))

 

 

3. Tip

 

String s에 대한 가정이 존재하는 경우에는 문제 풀이 방식이 달라질 수 있다.

charset이 작다면 HashSet/HashMap을 사용하는 것보다 boolean/integer array를 사용하는 것이 낫다.

물론 전자의 경우도 O(1)의 시간 복잡도를 지니지만, 상수 시간에서도 시간의 차이는 존재한다.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        Integer[] chars = new Integer[128];

        int left = 0;
        int right = 0;

        int res = 0;
        while (right < s.length()) {
            char r = s.charAt(right);

            Integer index = chars[r];
            if (index != null && index >= left && index < right) {
                left = index + 1;
            }

            res = Math.max(res, right - left + 1);

            chars[r] = right;
            right++;
        }

        return res;
    }
}