[알고리즘] #Longest Substring Without Repeating Characters

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

Loading...

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

 

 

 

---

반복되는 문자가 없는 가장 긴 문자열의 길이를 구하는 문제이다.

 

#이중 for문을 이용한 풀이

주어진 문자열을 Character 배열로 변환한 뒤에 한글자씩 비교하면서 반복되는 문자가 존재하는지 탐색한다.

public class Main {
    public static void main(String[] args) {

        Solution solution = new Solution();

        System.out.println("문자열 : " + "" + " ====> 가장 긴 길이 : " + solution.lengthOfLongestSubstring(""));
        System.out.println("문자열 : " + " " + " ====> 가장 긴 길이 : " + solution.lengthOfLongestSubstring(" "));
        System.out.println("문자열 : " + "au" + " ====> 가장 긴 길이 : " + solution.lengthOfLongestSubstring("au"));
        System.out.println("문자열 : " + "abcabcbb" + " ====> 가장 긴 길이 : " + solution.lengthOfLongestSubstring("abcabcbb"));
        System.out.println("문자열 : " + "bbbbb" + " ====> 가장 긴 길이 : " + solution.lengthOfLongestSubstring("bbbbb"));
        System.out.println("문자열 : " + "pwwkew" + " ====> 가장 긴 길이 : " + solution.lengthOfLongestSubstring("pwwkew"));

    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 주어진 문자열이 null이거나, 빈 값일 때
        if(s == null || s.length() == 0) {
            System.out.println(">>>> lonngestStr : 0");
            return 0;
        }

        // 주어진 문자열을 Char 배열로 변환
        char[] str = s.toCharArray();

        // 반복되는 문자가 없는 가장 긴 문자열
        String longestStr = "";

        for(int i=0; i<str.length; i++) {
            // 반복되는 문자가 없는 문자열
            String txt = Character.toString(str[i]);
            if(i==0) {
                longestStr = txt;
            }

            for(int j=i+1; j<str.length; j++) {
                // 반복되는 문자가 나타났을 때, 가장 긴 문자열과 비교해서 longestStr보다 길이가 긴 경우, txt로 값을 업데이트한다.
                if(txt.contains(Character.toString(str[j]))) {
                    if(txt.length() > longestStr.length()) {
                        longestStr = txt;
                    }
                    break;
                } else {
                    txt = txt.concat(Character.toString(str[j]));

                    if(txt.length() > longestStr.length()) {
                        longestStr = txt;
                    }
                }
            }
        }

        System.out.println(">>>> lonngestStr : " + longestStr);
        return longestStr.length();
    }
}

 

결과 값

>>>> lonngestStr : 0
문자열 :  ====> 가장 긴 길이 : 0
>>>> lonngestStr :           // " " 여백 한칸임
문자열 :   ====> 가장 긴 길이 : 1
>>>> lonngestStr : au
문자열 : au ====> 가장 긴 길이 : 2
>>>> lonngestStr : abc
문자열 : abcabcbb ====> 가장 긴 길이 : 3
>>>> lonngestStr : b
문자열 : bbbbb ====> 가장 긴 길이 : 1
>>>> lonngestStr : wke
문자열 : pwwkew ====> 가장 긴 길이 : 3