字符串的最长无重复字符的子串长度是什么

本篇文章给大家分享的是有关字符串的最长无重复字符的子串长度是什么，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。

题目描述：

对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。

给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。

测试样例：

"abcdbefgdchi",12

返回：8

这个题我研究了好半天，确实不好想，看了别人的思路，半天才把代码写出来

分析：

首先定义三个辅助变量：

max_len：表示字符串中最长无重复字符的子串长度，也就是函数返回值

map<char, int>：用来存放当字符串前位置的字符最近出现的位置

pre_len：用来存放当前位置之前最长无重复字符的子串长度

下面开始主逻辑

从字符串的起始处开始遍历

如果map中没有该字符，则将该字符及其下标插入到map中，并将pre_len++

再和max_len进行比较，取较大者赋给max_len

如果map中已经有了该字符，那么取出该字符对应的值（也就是该字符最近出现的下标）记为pos_A

当前下标减去pre_len记为pos_B，表示前面最长无重复字符子串的起始位置

这时候，pos_A和pos_B会有一下三种情况：

第一种情况：posA == pos_B

第二种情况：pos_A > pos_B

第三种情况：pos_A < pos_B

对于第一种情况来说，pre_len 大小不会改变。

对于第二种情况来说，pos_A 在 pos_B的右边，根据 pos_A 和 pos_B 所代表的含义可知道：

在距离当前很近的位置上，当前字符已经出现了重复，因此当前位置之前最长无重复字符子串的长度缩短了，如图所示：

因此，更新后的 pre_len 应该为 当前位置的下标减去 pos_A

对于第三种情况来说，pos_A 在 pos_B 的左边，根据 pos_A 和 pos_B 所代表的含义可知道：

在距离当前很远的位置上，当前字符出现了重复，这个位置比pos_B 还远，这么远的路径上，pos_B 处的字符早已出现了重复，因此当前位置之前最长无重复字符子串的长度应该为 当前位置到pos_A 的距离，如图所示

因此，更新后的 pre_len 应该为 当前位置的下标减去 pos_B + 1

更新后的pre_len 与max_len 进行比较，取其大者即可

注意，最后应该将map中当前位置字符的下标进行更新（千万不能漏掉）

于是乎一个完整的逻辑已经完成了，这样从头到尾遍历这个字符串，最终便可得到

字符串的最长无重复字符的子串长度 max_len

甚至还可以获得该字串，将其单独打印出来（这里留给读者自行实现，不难）

代码如下：

int longestSubstring(string A, int n) {
	if (A.size() <= 0 || n <= 0)
		return 0;

	int max_len = -1;
	int pre_len = 0;
	map<char, int> m;
	for (int i = 0; i < A.size(); ++i){
		if (m.count(A[i]) == 0){
			m.insert(pair<char, int>(A[i], i)); //map中不存在该字符，则直接插入
			++pre_len;
			if (pre_len > max_len)
				max_len = pre_len;
			continue;
		}
	
		map<char, int>::iterator iter_prev = m.find(A[i]);
		int pos_A = iter_prev->second;
		int pos_B = i - pre_len;
		
		if (pos_A > pos_B)
		{
			pre_len = i - pos_A;
		}
		else if (pos_B > pos_A)  //pos_A <= pos_B
		{
			pre_len = i - pos_B + 1;
		}
		else
		{
			//do nothing!
		}

		if (pre_len > max_len)
			max_len = pre_len;

		m[A[i]] = i;  //更新map
	}

	return max_len;
}

以上就是字符串的最长无重复字符的子串长度是什么，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。