[leetcode - Java] 3. Longest Substring Without Repeating Characters

1. 문제

---

- 중복되지 않은 연속된 문자의 가장 큰 길이를 구하여라

2. 의사 코드

---

비어있는 리스트를 생성하고 문자열 s를 char로 한 문자씩 빈 리스트에 중복 체크하여 넣고 리스트 길이를 출력하면 될 것 같았다.

1. 빈 리스트 생성
    ArrayList<Character> lists = new ArrayList<>();
2. 반복문으로 lists에 문자가 있는지 확인 후 추가
    for (int i=0; i<문자열s 길이; i++) {
        2-1 조건문으로 s의 문자 하나씩 lists에 있는지 확인
        2-2 없다면 추가        
    }

3. 시도

---

class Solution {
    public int lengthOfLongestSubstring(String s) {
        ArrayList<Character> lists = new ArrayList<>();

        for (int i=0; i<s.length(); i++) {
            if (!lists.contains(s.charAt(i))) {
                lists.add(s.charAt(i));
            }
        }
        System.out.println(lists);
        System.out.println(lists.size());
        return lists.size();
    }
}

어느정도 방향은 맞는듯 하다. 위 문제의 경우 wke가 lists에 들어가야했지만 연속되지 않은 문자 p도 들어가며 오류이다.

4. 개선

---

개선시 고려한 사항은 아래와 같다.

1. 반복문 안에서 list.contains() 함수를 실행하면 매 요청마다 리스트 전체를 확인 해야해 시간이 오래 걸릴 것이다.
   -> 각 문자에 고유한 인덱스(해시값)를 부여하는 HashSet이용??

2. 투 포인터 or 슬라이드 윈도우 방법(연속된 것을 구할 때 유용하다)

   class Solution {
    public int lengthOfLongestSubstring(String s) {
   
        int max = 0;
        int left = 0;
        HashSet<Character> set = new HashSet<>();
   
        for (int right=0; right<s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                // System.out.println("1 set = " + set);
                set.remove(s.charAt(left));
                // System.out.println("2 set = " + set);
                left++;
            }
            // System.out.println("3 set = " + set);
            set.add(s.charAt(right));
            // System.out.println("4 set = " + set);
            max = Math.max(max, set.size());
            // System.out.println("max = " + max);
        }
   
        return max;
    }
   }

   

이 문제를 개선할 때 전에 풀었던 leetcode 209번과 비슷한 방식을 적용하였다. 209번 문제는 인덱스 최솟값을 구해야 했기에 Integer.MAX_VALUE를 사용해 초기값을 큰 수로 설정 했었다면, 이번 문제의 경우 최댓값을 구해야 했기에 max를 0으로 초기화 했다.