[LeetCode- Ch4. 투 포인터] 1. 단어중복없는 가장 긴 문자열 #(+ 슬라이딩 윈도우)

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

Longest Substring Without Repeating Characters - LeetCode

 

 

1. rt를 이용해 문자열 길이까지 ++하면서 돈다.

2. 중복 처리 체크

3. 중복시 0으로 초기화

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        //1. ds
        Map<Character, Integer> map = new HashMap<>();
        int lt=0, rt=0;
        int cnt=0, max=0;
        
        //2 loop
        while(rt<s.length()){
            //문자열에서 rt를 이용 문자 추출해 map에 삽입
            char c = s.charAt(rt);
            map.put(c, map.getOrDefault(c, 0)+1);
            if(map.get(c) >1) cnt++;
            rt++;
            
            //cnt를 이용해 중복확인
            //: 중복 발생시 -> value부분 모두 0으로 초기화
            while(cnt>0){
                char c2=s.charAt(lt);
                if(map.get(c2)>1) cnt--;
                map.put(c2, map.get(c2)-1);
                lt++;
            }
            max=Math.max(max, rt-lt);
        }
        return max;
    }
}

---

Lis의 contains를 이용해, 해당문자가 리스트에 있을 때 없을 때까지 앞에서부터 차례대로 삭제

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //단어 중복이 없는 가장 긴 문자열
        //int lt=0;

        if(s.length()==0 || s==null) return 0;
        List<Character> list = new ArrayList<>();
        int n=s.length();
        int answer=Integer.MIN_VALUE;
        
        for(int rt=0; rt<n;rt++){
            while(list.contains(s.charAt(rt))){
                list.remove(0);
            }
            list.add(s.charAt(rt));
            // for(char c:list)System.out.print(c+" ");
            // System.out.println();
            
            answer=Math.max(list.size(), answer);
        }

        return answer;
    }
}

 

+) 세련된 풀이

 

1) Map의 getOrDefault 이용한 풀이

class Solution {
    public int lengthOfLongestSubstring(String s) {
		Map<Character, Integer> map = new HashMap<>();
		int left = 0, right = 0, counter = 0, max = 0;

		while (right < s.length()) {
			char c = s.charAt(right);
			System.out.println("c: " + c);
			map.put(c, map.getOrDefault(c, 0) + 1);
			if (map.get(c) > 1)
				counter++;
			right++;

			while (counter > 0) {
				char charTemp = s.charAt(left);
				if (map.get(charTemp) > 1)
					counter--;
				map.put(charTemp, map.get(charTemp) - 1);
				left++;
			}
			max = Math.max(max, right - left);
			System.out.println("max "+max);
		}
		return max;
	}
}

 

2) 배열을 이용한 풀이

class Solution {
    public int lengthOfLongestSubstring(String s) {
		int[] map = new int[128];
		int start = 0, end = 0, maxLen = 0, counter = 0;

		while (end < s.length()) {
			char c1 = s.charAt(end);
			if (map[c1] > 0) counter++;
			map[c1]++;
			end++;

			while (counter > 0) {
				char c2 = s.charAt(start);
				if (map[c2] > 1) counter--;
				map[c2]--;
				start++;
			}

			maxLen = Math.max(maxLen, end - start);
		}

		return maxLen;
	}
}

 

3) Map의 containsKey 이용한 풀이

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