即找到具有不重复字符的最长子字符串。
例如ABDEFGABEF的具有不重复字符的子字符串可以是BDEFGA, 也可以是ABDEFG， 或者是DEFGAB， 长度是6。 可见LSRC是不唯一的。
主要有两个解决办法。
方法一（bruteforce） 我们通过检查给定字符串的所有子字符串，看看每一个子字符串是否包含着unique的字符。 然后输出满足所有字符都是唯一的子字符串中最长的哪一个就可以了。
不难看出， 总共有 n (索引从0开始的子字符串的个数) + (n – 1) (索引从1开始的子字符串的个数)+ …… + 1 = （n + 1）n /2。 检查一个子字符0串是是否满足unique characters的要求，我们可以在线性时间内check 完。 也就是维护一个map记录下从前到后扫描子字符串的时候， visited 过的字符。 这个map最开始每一个元素初始化为-1， 一旦碰见了， 就更新为1， 表示这个字符已经在这个子字符串里面存在了。 这样， 我们就可以在线性时间内判断一个子字符串是否具有unique的character了。 扫描的最坏时间为O（n）， 所以这个办法的时间复杂度为O（n^3）， 不好。
方法二：(线性时间求解) 动态规划：移动窗口。
我们可以在线性时间内找到一个字符串的LSRC。 具体的做法就是用空间换取时间。
首先我们从左往右扫描给定的字符串， 记录下到目前为止看到的最长的Non-Repeating Character Substring(NRCS)。 令其长度为max_len。 然后我们扫描，， 同时用cur_len记录下当前的（current）NRCS的长度。 对于每一个新来的字符， 我们在临时数组visited[]（存放和新加进来的字符相同的那个字符的位置）查找这个字符是否已经被处理过了。 如果在visited中还没有见过（没被访问过）， 我们就把cur_len加1。 否则， 说明这个字符已经见过了。此时， 处理办法有如下两个case。
case 1: 之前出现的那个字符(即与新加进来的那个字符相同）不属于当前的NRCS(the NRCS which is under process)， 此时我们只需要对cur_len加1即可。
case 2: 如果之前出现的那个字符属于当前的NRCS的， 那么我们当前的NRCS就会发生变化。 NRCS就变成了从之前出现的那个字符的下一个字符为起点， 到当前这个新加入的字符了。
另外，在改变当前的NRCS之前（或者是改变cur_len之前）， 都需要把cur_len和max_len进行比较。
程序如下：
#include <cstdlib>#include <cstdio>#include <cstring> // for strlen function#define NO_OF_CHARS 256int min(int a, int b);int longestUniqueSubsttr(char *str) {int n = strlen(str);int cur_len = 1; // To store the lenght of current substringint max_len = 1; // To store the resultint prev_index; // To store the previous indexint i;int *visited = new int[NO_OF_CHARS];/* Initialize the visited array as -1, -1 is used to indicate thatcharacter has not been visited yet. */for (i = 0; i < NO_OF_CHARS; i++)visited[i] = -1;/* Mark first character as visited by storing the index of firstcharacter in visited array. */visited[static_cast<int>(str[0])] = 0; // 第一个见到的字符串位于0处/* Start from the second character. First character is already processed(cur_len and max_len are initialized as 1, and visited[str[0]] is set */for (i = 1; i < n; i++) {prev_index = visited[static_cast<int>(str[i])];/* If the currentt character is not present in the already processedsubstring or it is not part of the current NRCS, then do cur_len++ */// …prev_index… cur_len iif (prev_index == -1 || i – cur_len > prev_index)cur_len++;/* If the current character is present in currently considered NRCS,then update NRCS to start from the next character of previous instance. */else{/* Also, when we are changing the NRCS, we should also check whetherlength of the previous NRCS was greater than max_len or not.*/// cur_len和max_len相比较if (cur_len > max_len) // 更新max_lenmax_len = cur_len;// 更新当前的cur_lencur_len = i – prev_index;}// i is prev_index of character str[i]visited[static_cast<int>(str[i])] = i; // update the index of current character}// Compare the length of last NRCS with max_len and update max_len if neededif (cur_len > max_len)max_len = cur_len;delete[] visited; // free memory allocated for visitedreturn max_len;}/* A utility function to get the minimum of two integers */int min(int a, int b){return (a>b)?b:a;}/* Driver program to test above function */int main(){char str[] = "ABDEFGABEF";printf("The input string is %s \n", str);int len = longestUniqueSubsttr(str);printf("The length of the longest non-repeating character substring is %d", len);return 0;}
运行结果如下：
时间复杂度：
Time Complexity:O(n + d) where n is length of the input string and d is number of characters in input string alphabet. For example, if string consists of lowercase English characters then value of d is 26.Auxiliary Space:O(d)Algorithmic Paradigm:Dynamic Programming
背着背包的路上，看过许多人，
