【LeetCode】003 Longest Substring Without Repeating Characters最長重複しないサブ文字列

3783 ワード

【LeetCode】003 Longest Substring Without Repeating Characters
タイトル
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 and not a substring.
構想
AC
import java.util.*;
public class Solution {
    //   ,   
    public int lengthOfLongestSubstring0(String s) {
        int maxLen = 0;
        List subList = new ArrayList<>();
        for (int i = 0; i < s.length(); i ++){
            char ch = s.charAt(i);
            int index = subList.indexOf(ch);
            if (index != -1){
                if (maxLen < subList.size()) maxLen = subList.size();
                if (index == subList.size()-1) subList.clear(); 
                else                           subList = subList.subList(index+1, subList.size());
            }

            subList.add(ch);
        }
        if (maxLen < subList.size()) maxLen = subList.size();
        return maxLen;
    }



    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        StringBuilder sub = new StringBuilder(s.length());
        int fromIndex = 0;

        for (int i = 0; i < s.length(); i ++){
            char ch = s.charAt(i);

            int index = sub.indexOf(ch+"", fromIndex);  //   “  ”(   )    

            if (index != -1) fromIndex = index+1;  //         

            sub.append(ch);

            int len = sub.length() - fromIndex;  //     -      =          

            if (maxLen < len) maxLen = len;
        }

        return maxLen;
    }
}