无重复字符的最长子串

1：解题思路
因为是子串，那任意子串的结尾字符一定是原始字符串中的其中一个字符。所以只需求出每个字符，以它结尾的最长无重复字符长度，再取最大长度即可。再借助动态规划思想，下一个字符的最长无重复可由上一个字符的最长无重复子串推出，即比较当前字符串上一次出现的位置pi和上一个字符最长不重复子串的开始位置li，即可算出当前字符的最长无重复子串开始位置。

package com.nobody;

/**
 * 题目：
 * 无重复字符的最长子串
 * 描述：
 * 给定一个字符串，找出其中不含有重复字符的 最长子串 的长度。
 * 示例：
 * 输入: "abcabcbb"
 * 输出: 3
 * * 输入: "bbbbb"
 * 输出: 1
 * * 输入: "pwwkew"
 * 输出: 3
 * @author Μr.ηobοdy
 *
 * @date 2020-03-28
 *
 */
public class LengthOfLongestSubstring { public static void main(String[] args) { System.out.println("au:" + lengthOfLongestSubstring("au")); System.out.println("abcabcbb:" + lengthOfLongestSubstring("abcabcbb")); System.out.println("bbbbb:" + lengthOfLongestSubstring("bbbbb")); System.out.println("pwwkew:" + lengthOfLongestSubstring("pwwkew")); } public static int lengthOfLongestSubstring(String s) { if (null == s || "".equals(s)) { return 0; } int maxLen = 1; char[] chars = s.toCharArray(); // 猜想字符串都是单字节字符,单字节字符只有128位，这样效率快 // 否则需要用map进行记录 int[] preIndex = new int[128]; // 初始化每个字符上一个出现在字符串位置都不存在，即-1 for (int i = 1; i < preIndex.length; i++) { preIndex[i] = -1; } // 字符串的第一个字符特殊处理，即该字符上一次出现的位置即当前位置 preIndex[chars[0]] = 0; // chars[i-1]字符结尾的最长不重复子串的开始索引 int li = 0; for (int i = 1; i < chars.length; i++) { int pi = preIndex[chars[i]]; if (pi >= li) { li = pi + 1; } // 更新这个字符最后出现的位置 preIndex[chars[i]] = i; // 比较最长字符串的长度 maxLen = Math.max(maxLen, i - li + 1); } return maxLen; }

}


  

 

  
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
 

文章来源: javalib.blog.csdn.net，作者：陈皮的JavaLib，版权归原作者所有，如需转载，请联系作者。

原文链接：javalib.blog.csdn.net/article/details/105172083