[LeetCode] 3. Longest Substring Without Repeating CharactersMedium - Medium

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

Longest Substring Without Repeating Characters - LeetCode

 

문제 설명

주어진 string s에서 반복되는 character가 없는 최대 길이의 substring을 찾는 것!

0 <= s의 길이 <=5*10^4

s는 영어 대소문자, 숫자, 기호, 공백으로 이루어져있음.

 

 

문제 풀이 1. List 활용 for문 2개 + contains method 활용 - Time Limit Exceeded

시간복잡도는 O(n^2), characterList의 길이는 한정되어 있으므로 ㅇㅇ

for문을 하나씩 돌면서 특정 index에서의 가장 긴 substring을 찾아보았다.

단순 무식하기때문에 가장 느리다.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        ArrayList<Character> charList = new ArrayList<>();
        int max=0;
        for(int j=0; j<s.length(); j++){
            charList = new ArrayList<>();
            for(int i=j; i<s.length(); i++){
                if(charList.contains(s.charAt(i))){
                    if(max<charList.size()){
                        max=charList.size();
                    }
                    charList = new ArrayList<>();
                }
                charList.add(s.charAt(i));
            }
            if(max<charList.size()){
                max=charList.size();
            }
        }
        return max;
    }
}

 

문제 풀이 2. Queue 활용

Queue에 Character를 하나씩 넣으면서, 기존에 나왔던 character일 경우, 

해당 character 전까지 poll 해준다.(날려준다.)

이 중 길이가 최대 인 것을 찾아가는 풀이 방법.

예시)

s = "abcabcbb"

queue 변화
[a]
[a, b]
[a, b, c]
[b, c, a]
[c, a, b]
[a, b, c]
[c, b]
[b]

 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Queue<Character> queue = new LinkedList<>();
        int max=0;
        
        for(int i=0; i<s.length(); i++){
            if(queue.contains(s.charAt(i))){
                if(max<queue.size()){
                    max=queue.size();
                }
                // 지우는게 O(n);?까지는 아니고, English letters, digits, symbols and spaces의 수.
                while(queue.poll()!=s.charAt(i)){
                }
            }
            queue.add(s.charAt(i));
            // System.out.println(queue);
        }
        if(max<queue.size()){
            max=queue.size();
        }


        return max;
    }
}

문제 풀이 3. start, end index 활용

class Solution {
    public int lengthOfLongestSubstring(String s) {
    int max=0;
    for(int start=0, end=0; end<s.length(); end++){
        int loc = s.indexOf(s.charAt(end), start); // start부터 시작해서 character의 index 리턴.
        
        if(loc!=end){
            // start의 index를 update해준다.
            start = loc+1;
        }
        max = Math.max(max, end-start+1);
    }
    

    return max;
    }
}