[LeetCode] 3. Longest Substring Without Repeating Characters

1. 문제

 

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.

 

 

---

2. 배운점

 

 

1. String에 charAt 이라는 메서드가 있어서, 그 인덱스의 값을 뽑아올 수 있다. 다만 반환 타입은 char 이여야한다. 변환을 위해서는 String.valueOf() 메서드를 이용해야한다.

2. String에 contains 메서드가 있다.

3. ArrayList에 sort 메서드가 있다. compare 메서드를 override하여서 Comparator로 사용할 수 있다. 기준이 되는 데이터가 큰 경우 양수, 같은경우 0, 작은 경우 음수를 리턴해야한다.

-> desc로 정렬하고 싶다면, 양수와 음수를 반대로 넣어주면 된다!

 

4. String.concat() 메서드는 값을 저장해주지 않는다. 필요하다면 String result = result.concat(ch) 와 같이 재할당이 필요하다.

list.sort(new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int size1 = s1.size();
                int size2 = s2.size();
                
                if(size1 == size2) return 0;
                else if(size1 > size2) return 1;
                else return -1;
            }
        });

 

 

---

3. 풀이

 

나의 풀이

 

brute force와 같은 방법으로 Time complexity 는 O(N^2)이다.

    class Solution {

        public int lengthOfLongestSubstring(String s) {
            //0 위치부터 substring을 하되, 같은 char이 나오면 중단 후 substring 저장
            //1위치부터 반복

            int startIdx = 0;
            String resultSubstring = "";
            List<String> result = new ArrayList<>();

            while(startIdx < s.length()) {
                for(int i = startIdx; i < s.length(); i++) {
                    String ch = String.valueOf(s.charAt(i));
                    if(!resultSubstring.contains(ch)) {
                        resultSubstring = resultSubstring.concat(ch);
                    } else {
                        result.add(resultSubstring);
                        startIdx++;
                        resultSubstring = "";
                        break;
                    }
                }
            }
            
            if(result.isEmpty()) {
                return 0;
            } else {
                result.sort(new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    int size1 = s1.length();
                    int size2 = s2.length();

                    if(size1 == size2) return 0;
                    else if(size1 > size2) return -1;
                    else return 1;
                }
            });

            return result.get(0).length();
            }

            
        }
    }

 

 

4. 해답

 

sliding window라고 부르는 알고리즘을 사용한다. sliding window는 특정 array나 string의 요소들을 차례대로 조회할 때 많이 쓰는 전략이다. window는 특정한 범위를 말한다. array에서 특정 index의 범위를 [i, j]로 선정한다면, 전체 길이에 비해서 해당 범위만 관찰하므로 이 부분을 window라고 비유하여 설명한다.

 

이 문제에서는 중복되는 알파벳이 없는 최대 길이의 substring을 구해야하는데, 이를 해결하기 위해 window 개념을 사용한다. 처음 index부터 하나씩 올라가다가, 중복되는 알파벳이 나오는 부분까지만 범위(window, [i, j])를 지정하고 중복되는 알파벳이 나오면 window를 한칸씩 밀어서([i+1, j+1]) 이동하면 되는 개념이다.

 

뭔가 배열이나 String이 나오면 index를 그리는 i, j를 머릿속에서 상상해보면 생각하는데 도움이 될 것 같다.

 

 

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;
    }
}

 

분석

HashMap을 이용해서 중복된 항목이 없도록 만든다. window의 크기를 늘려나가는(j++) index인 j값이 map에 있다면, 중복된 알파벳이 나온 것으로 간주하여 i값을 처음 알파벳이 나왔던 위치에서 j+1의 위치로 옮긴다. 

 

예를 들어 "abca" 라는 문자열을 생각해보면 Map에 최초로 들어가는 값은 (a, 1) 이다. 그리고 (b, 2), (c, 3)이 차례로 들어간 후, index가 3인 4번째의 a가 나오면 i값을 3으로 만드는 것이다. 그렇게 window를 sliding 하는 방식으로 총 길이값을 ans 값으로 반환한다.

 

주목해야할 기술 포인트들이 있다.

• index 대비 +1을 해야 i "번째" 항목이 된다. 당연하지만, 익숙해져야할 것 같다.
• i, j로 순환하며 map에 j+1 값을 put하여 i값으로 전달한다.
• Math.max를 이용해서 인덱스(i)값을 큰 쪽으로 옮겨갈 수 있으며, 기존에 구해놓은 ans값 대비 새로 구하는 j - i + 1 길이값과 비교하여 항상 최대값을 반환하도록 만들 수 있다.

 

 

---

 

 

참조

 

https://leetcode.com/problems/longest-substring-without-repeating-characters/