/*
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.
*/
public class Solution {
public static int lengthOfLongestSubstring(String s) {
//如果是空的话 返回0
if(s == null || s.length() == 0 ){
return 0;
}
//如果只有一个字符 返回1
int length = s.length();
if(length == 1){
return 1;
}
//记录最大的长度
int ret = 0;
for (int i = 0; i <length; i++) {
//获取当前下标的字符 例："abcdefd" 当i=2的时候 获取的是"c"
String temp =s.substring(i,i+1) ;
for (int j = i+1; j <length; j++) {
if(temp.indexOf(s.substring(j,j+1)) == -1){
//如过没包含的字符 就改变temp 比如开始i=2 temp是"c" j从3开始 "c".indexOf("d"); 结果是-1 temp="c"+"d"; 依次类推 直到indexOf的结果不为-1
//这里可以用串 也可以把所有字符放到set中
temp = s.substring(i,j+1);
if(temp.length() > ret){
ret = temp.length();
}
}else{
if(temp.length() > ret){
ret = temp.length();
}
break;
}
}
}
return ret;
}
/*
* 这个是在网上看到的解决办法 感觉很好 非常好 比我的好多了
*
* 这个的整体思路是从0开始遍历这些字符 i记录不重复字串的最前边的下标 j记录最后边的下标 每向后遍历一个字符就计算一下最大长度 赋值给ans
* 如果字串没有重复的字符就j++ 如果有重复的就从set中开始删除（从i开始 因为i是字串的首字符下标）
*
* 举个例子来说：abcddrt
* 开始遍历： (1)a i=0; j=0
* (2)ab i=0; j=1
* (3)abc i=0; j=2
* (4)abcd i=0; j=3
* (5)abcd d 有重复的字符了 开始从set中删除字符 i=0 j=4
* (6)bcdd i=1; j=4
* (7)cdd i=2; j=4
* (8)dd i=3; j=4
* (9)d i=4; j=4 没有重复的了 又开始j++了
* (10)dr i=4 j=5
* loop...
*/
public int lengthOfLongestSubstring2(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
//取最大值
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
/**
*
*网上看见的 是用map实现的 也是挺好的一个方案
*我感觉这个方案核心的地方就是 怎么计算字串的最大长度 好吧 这是问题所在 说了一句废话
*把所有的字符都以key-value 的形式存到map中 key:字符 value：字符距当前遍历下标的最近的下标 比如abcdbf 如果遍历到第二个b的时候 key:b value:4
*i是什么呢 i是记录不重复字串的首首字符下标 比如： abcdfdas 遍历到c的时候 i=0 遍历到第二个d的时候i就会变成5
*遍历过程中 如果map中存在当前遍历的字符 就看这个字符的下标和i的下标 谁大 取大值
*
*例子：abcdbag
*(1)map:{a:1} i=0 j=0;
*(2)map:{a:1,b:2} i=0 j=1;
*(3)map:{a:1,b:2,c:3} i=0 j=2;
*(4)map:{a:1,b:2,c:3,d:4} i=0 j=3;
*(5)map:{a:1,b:4,c:3,d:4} i=2 j=4; 注意了：b:4 i=2 因为b重复了所以b的下标要改成当前下标
* i=取最大值（b的下标，i） 第一次i是0 肯定是b的下标大 i=2 i 记录的就是上次重复的字符的下标（靠近字符串尾部的）
*(6)map:{a:6,b:4,c:3,d:4} i=2 j=5; a重复了 但是i不能用a的下标 因为上次重复的地方在a后边 所以这次i=2
* loop。。。。
* 我这个文字表达能力不是很好 如果有问题 可以留言沟通交流
*2017年8月27日 下午12:59:28
*/
public int lengthOfLongestSubstring3(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
/**
*
* 这个跟map差不多 是用index[] 数组来代替map
*2017年8月27日 下午1:58:48
*/
public int lengthOfLongestSubstring4(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
public static void main(String[] args) {
//测试
System.out.println(Solution.lengthOfLongestSubstring("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghCD"));
}