无重复字符的最长子串

无重复字符的最长子串

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

示例 1:

输入: s = “abcabcbb”
输出: 3
ps: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
ps: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

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

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

思路：

无重复子串，即各种字母进行相同切割，然后得出最长串，那么就判断最长字母切割的串是多长

package demo_2;

import java.util.HashMap;
import java.util.Map;

/**
 * 类描述：无重复字符的最长子串
 *
 * @author lwj
 */
public class Demo_2 {
    public static void main(String[] args) {
        String motherString = "assbcssassbsscddbssdssccbssdwe";

        Map<Character, Integer> pointMap = new HashMap<Character, Integer>();
        int maxLength = 0;
        int strStart = 0;
        String maxStr = "";
        /* 转换为数组，遍历出每个元素出现的位置，并记录
         * 如果出现过，则判断该串长度大小，进行截取*/
        char[] chars = motherString.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            if (pointMap.containsKey(aChar)) {
                strStart = Math.max(pointMap.get(aChar) + 1, strStart);
            }
            if (i - strStart >= maxLength) {
                maxLength = i - strStart;
                maxStr = motherString.substring(strStart, i + 1);
            }
            pointMap.put(aChar, i);
        }
        System.out.println("最长字符串: " + maxStr);
        System.out.println("长度为：" + (maxLength + 1));
    }
}
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