[leetcode] Medium-3번. longest-substring-without-repeating-characters 문제풀이

문제

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

Longest Substring Without Repeating Characters - LeetCode

 

 

 

풀이코드

import java.util.*;

/**
 * https://leetcode.com/problems/longest-substring-without-repeating-characters/
 */
public class M002_leetCode3_Longest_Substring {
    ListNode resultNode = new ListNode();

    public static void main(String[] args) {
        M002_leetCode3_Longest_Substring solution = new M002_leetCode3_Longest_Substring();
        System.out.println(solution.lengthOfLongestSubstring("dvdf"));
        //System.out.println(solution.lengthOfLongestSubstring("abcabcbb"));
    }

    public int lengthOfLongestSubstring(String s) {
        /* 중복 데이터가 들어가지않는 Set 사용 */
        Set<Character> set = new HashSet<Character>();
        int size = s.length();

        int start = 0;
        int end = 0;

        int[] dp = new int[size + 1];

        while (end < size) {
            if (set.contains(s.charAt(end))) { /* 현재 target 이 이미 담겨져있을 경우 */
                set.remove(s.charAt(start)); /* start 지점의 문자 제거 */
                start = start + 1;
            } else { /* 새로운 문자의 경우 */
                set.add(s.charAt(end)); /* Set 에 문자를 담고 */
                end = end + 1; /* target 을 그 다음으로 넘기고 */
                dp[end] = end - start; /* end - start (현재의 문자열 개수) 를 dp 에 담는다 */
            }
        }

        return Arrays.stream(dp).max().getAsInt(); /* 최대값 추출 */
    }
}