一、题目：给定一个字符串，找出其中不含重复字符的最长子串的长度：

二、举例：

比如"abcdefgh",不含重复字符的最长子串为eacdb,长度为8；比如"abceacdb",不含重复字符的最长子串为eacdb,长度为5；比如"aaaabcbb",不含重复字符的最长子串为abc,长度为3；比如"pwwkewww",不含重复字符的最长子串为wke或kew,长度为3；比如"bbbbbbbb",不含重复字符的最长子串为b,长度为1;比如"",不含重复字符的最长子串没有,长度为0

三、解析推导：

假设字符串长度为8，如果是从左往右开始遍历找寻的话：

找最长为8的满足条件的子串，需遍历1次，因为长度为8的原字符串最多只包含1个长度为8的不同子串，因为【从左往右】找到的【最后一个长度为8的字符串】的【头字符】，是【原字符串】【从左往右数】的第1个字符，若遍历过程中只要有满足条件的，则返回8并退出，否则继续；找最长为7的满足条件的子串，需遍历2次，因为长度为8的原字符串最多只包含2个长度为7的不同子串，因为【从左往右】找到的【最后一个长度为7的字符串】的【头字符】，是【原字符串】【从左往右数】的第2个字符，若遍历过程中只要有满足条件的，则返回7并退出，否则继续；找最长为6的满足条件的子串，需遍历3次，因为长度为8的原字符串最多只包含3个长度为6的不同子串，因为【从左往右】找到的【最后一个长度为6的字符串】的【头字符】，是【原字符串】【从左往右数】的第3个字符，若遍历过程中只要有满足条件的，则返回6并退出，否则继续；找最长为5的满足条件的子串，需遍历4次，因为长度为8的原字符串最多只包含4个长度为5的不同子串，因为【从左往右】找到的【最后一个长度为5的字符串】的【头字符】，是【原字符串】【从左往右数】的第4个字符，若遍历过程中只要有满足条件的，则返回5并退出，否则继续；找最长为4的满足条件的子串，需遍历5次，因为长度为8的原字符串最多只包含5个长度为4的不同子串，因为【从左往右】找到的【最后一个长度为4的字符串】的【头字符】，是【原字符串】【从左往右数】的第5个字符，若遍历过程中只要有满足条件的，则返回4并退出，否则继续；找最长为3的满足条件的子串，需遍历6次，因为长度为8的原字符串最多只包含6个长度为3的不同子串，因为【从左往右】找到的【最后一个长度为3的字符串】的【头字符】，是【原字符串】【从左往右数】的第6个字符，若遍历过程中只要有满足条件的，则返回3并退出，否则继续；找最长为2的满足条件的子串，需遍历7次，因为长度为8的原字符串最多只包含7个长度为2的不同子串，因为【从左往右】找到的【最后一个长度为2的字符串】的【头字符】，是【原字符串】【从左往右数】的第7个字符，若遍历过程中只要有满足条件的，则返回2并退出，否则直接返回1即可；

四、总结归纳：

外层循环递减字符串长度，记为len;内层嵌套遍历检查符合长度len的每个字符串是否满足要求；通过上述解析推导过程，可以得出内层嵌套遍历的次数count=原字符长度+1-len

五、示例代码

import java.util.HashSet;import java.util.Set;import org.mons.util.StringUtils;public class MaxLengthOfDistinctSubStr_V1 {/**检测字符串是否有重复字符串*/public static boolean checkStr(String str){char[] c = str.toCharArray();// TODO 后续考虑用HashMap替换，因为HashSet底层也还是包装了一个HashMap Set set = new HashSet();for(int i = 0; i < c.length; i++) {set.add(c[i]);}if(set.size() == str.length()) {return true;}return false;}/**获取字符串的不重复字符的最长子串的长度*/public static int getMaxLengthOfDistinctSubStr(String str) {if(StringUtils.isBlank(str)) {System.out.format("str=%s:tmpStr=%s:%s\n",str,str,str.length());return 0;}if(checkStr(str)) {System.out.format("str=%s:tmpStr=%s:%s\n",str,str,str.length());return str.length();}//外层循环递减字符串长度，内层嵌套遍历检查符合长度的每个字符串是否满足要求(需计算出每个长度对应的遍历次数)，满足则返回//外层若递减到为2的长度还没找到，则直接退出外层循环即可，此时已经可以确定【不含重复字符的最长子串的长度】为1，因为其他情况都已经被排除完了for(int len=str.length()-1; len>=2; len--) {for(int count=0; count<=str.length()-len; count++) {int end=len+count;String tmpStr = str.substring(count, end);if(checkStr(tmpStr)) {System.out.format("str=%s:count=%s:tmpStr=%s:%s\n",str,count,tmpStr,tmpStr.length());return tmpStr.length();}}}return 1;}public static void main(String[] args) {getMaxLengthOfDistinctSubStr("abcdefgh");getMaxLengthOfDistinctSubStr("");getMaxLengthOfDistinctSubStr("abceacdb");getMaxLengthOfDistinctSubStr("aacabcbb");getMaxLengthOfDistinctSubStr("pwwkewww");getMaxLengthOfDistinctSubStr("bbbbbbbb");}}

六、执行结果

七、解题过程分享

一定要多读题!!!多读题!!!多读题!!!

把题目给出的要素、题目要得到的结果、以及要素和结果之间的逻辑关系，一一理解透彻，然后结合所掌握的知识尝试进行解答。比如本题，题目给出的要素是字符串，题目要得到的结果是：字符串里不含重复字符的最长子串的长度、关键在于如何将要素和结果之间的逻辑关系梳理清晰。其实在给出题目的同时已经给出了解题的思路， 就看如何把思路清晰的梳理出来。本题是通过一步步的分析推导，然后再尝试把分析推导的过程转化成代码(先外层循环递减字符串长度，再内层嵌套遍历检查符合长度len的每个字符串是否满足要求(想到了利用HashSet集合保证元素不重复的特性，来实现该检测))。一开始原本打算直接上手编写代码，却根本毫无头绪，无从下手，只能再去回头好好分析题目，慢慢有点眉目，然后想着把思路推导过程一步步写下来，再对着推导过程进行总结归纳， 这才侥幸解出本题。V1版本只是初步尝试解题，还需要再设法优化，再接再厉~

八、优化版本V2(已发布)

可以对比下两个版本的解题思路有何差异，只是思路转变了一下，代码效率差别如此之大，算法的魅力可见一斑，迷~

如果觉得《【每日一练及解题思路V1】给定一个字符串 找出其中不含重复字符的最长子串的长度》对你有帮助，请点赞、收藏，并留下你的观点哦！