文字列の中で最大連続して重複しない文字列を検索する(Longest Substring Without Repeating Characters)_By leetCode

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

Examples: Given “abcabcbb”, the answer is “abc”, which the length is 3. Given “bbbbb”, the answer is “b”, with the length of 1. Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence
1つの文字の中で最大連続して重複しない文字列を検索

One

public int lengthOfLongestSubstring(String s) {
        Set set = new HashSet<>();

        char[] charList = s.toCharArray();

        int length = 0;
        int sum =0;
        for (int i = 0,j=0; i < charList.length; i++) {
            if (set.contains(charList[i])){
                sum = set.size();
                set.clear();
                j++;
                i = j;
                set.add(charList[j]);
                length = Math.max(length , sum);
            }else {
                set.add(charList[i]);
                if (i == charList.length-1){
                    sum = set.size();
                    length = Math.max(length , sum);
                }
            }
        }

        return length;
    }

解析:HashSetを作成し、対応する文字を格納し、最大長を返します.

Two

public int lengthOfLongest(String s){
        int n = s.length(), ans = 0;

        int[] index= new int[128];

        for (int current = 0,start=0; current < n; i++) {
            start = Math.max(index[s.charAt(current)],start);
            ans = Math.max(ans ,current-start+1);
            index[s.charAt(current)] = current+1;
        }
        return ans;
    }

解析:startで繰り返し文字の次の開始位置をマークし、current+1で現在位置をマークします.current+1-startが今回のループの最大値です.

備考

int[26] for Letters ‘a’ - ‘z’ or ‘A’ - ‘Z’

int[128] for ASCII

int[256] for Extended ASCII