3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

首次代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package com.bd.leetcode.leetcode_3;

import java.util.*;

/**
 * @author 
 * @date: 2020/7/7
 */

/**
 * 1.该题可以用动态划块解决，startIndex表示划块起始位置，endIndex为结束为止
 * 2.stringBuffer为动态划块中字符串的内容
 * 3.每次循环endIndex加1，如果stringBuffer包含sArr[endIndex]，使用for循环查找最后一次该值在sArr中出现的位置，并将startIndex+1作为该值的起始位（substr时候去掉该值）
 */
class Solution {
  public int lengthOfLongestSubstring(String s) {
    String aStr = s;
    char[] sArr = aStr.toCharArray();
    StringBuffer stringBuffer = new StringBuffer();
    String max = null;
    int maxLength = 0;

    if (0 == sArr.length) {
      maxLength = 0;
    }

    if (1 == sArr.length) {
      maxLength = 1;
    }

    int startIndex = 0;
    int endIndex = 0;

    int i = 0;
    while (i < sArr.length) {

      if (!stringBuffer.toString().contains(sArr[i] + "")) { //不包含sArr[endIndex]，增加划块长度
        endIndex++;
        if (endIndex - startIndex > maxLength) {
          maxLength = endIndex - startIndex;
          max = aStr.substring(startIndex, endIndex);
        }
        stringBuffer.delete(0, stringBuffer.length()).append(aStr.substring(startIndex, endIndex));
      } else {//包含startIndex增加，直到sArr[i]不再被包含
        while (endIndex <= i && startIndex < endIndex) { //endIndex表示新加入的char，用循环获取最后一次出现的位置
          for (int j = endIndex - 1; j >= 0; j--) {
            if (sArr[j] == sArr[endIndex]) {
              startIndex = j + 1;
              break;
            }
          }
          endIndex++;
          stringBuffer.delete(0, stringBuffer.length()).append(aStr.substring(startIndex, endIndex));
        }
      }
      i++;
    }
    //最长连续
    //System.out.println(max);
    return maxLength;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    int len = s.lengthOfLongestSubstring("aab");
    System.out.println(len);
  }
}