最长子字符串，时间限制超过java

Question

给定一个字符串，在不重复字符的情况下，找到最长子字符串的长度。例如，“abcabcbb”的不重复字母的最长子字符串是“abc”，其长度为3。对于“bbbbb”，最长的子字符串是“b”，长度为1。

public static int lengthOfLongestSubstring(String s) {
    if (s.length()==0)
        return 0;
    int maxlen = 1;

    HashMap<Character, ArrayList<Integer>> check = new HashMap<Character,ArrayList<Integer>>();
    for (int i = 0; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            if (!check.containsKey(s.charAt(j))) {
                ArrayList<Integer> value= new ArrayList<>();
                value.add(j);
                check.put(s.charAt(j), value);
            }
            else {
                maxlen = Math.max(j - i, maxlen);
                ArrayList<Integer> temp = check.get(s.charAt(j));
                i=temp.get(temp.size()-1);  
              // get the last index(biggest index) of the key value
                check.clear();
                break;
            }
            if(j==s.length()-1) {
                maxlen = Math.max(j - i + 1, maxlen);
            }

        }
    }
    return maxlen;
  }
}

对于长可重复字符串的最后一次测试，超过了时间限制。不知道如何优化。寻求改进，谢谢

Answer 1

这里有一个相当简单的解决方案，它应该比您的解决方案更快：

public static int longestNonRepeating(final String s) {
    final Set<Character> unique = new HashSet<>();
    int max = 0;
    for (int i = 0; i < s.length(); ++i) {
        final char c = s.charAt(i);
        if (!unique.add(c)) {
            for (int j = i - unique.size(); j < i; ++j) {
                if (s.charAt(j) != c) {
                    unique.remove(s.charAt(j));
                } else {
                    break;
                }
            }
        }
        max = Math.max(max, unique.size());
    }
    return max;
}

这是怎么工作的？

我们沿着字符串走，并将字符添加到集中。如果我们添加的字符已经包含在set中，那么我们知道在当前子字符串中有一个重复的字符。

a  b  c  a  b  c
0  1  2  3  4  5
^
|
i

a  b  c  a  b  c
0  1  2  3  4  5
   ^
   |
   i

a  b  c  a  b  c
0  1  2  3  4  5
      ^
      |
      i

a  b  c  a  b  c
0  1  2  3  4  5
^        ^
|        |
j        i

a  b  c  a  b  c
0  1  2  3  4  5
   ^        ^
   |        |
   j        i

a  b  c  a  b  c
0  1  2  3  4  5
      ^        ^
      |        |
      j        i