字符串的最長無重復字符的子串長度是什么

本篇文章給大家分享的是有關字符串的最長無重復字符的子串長度是什么，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

題目描述：

對于一個字符串,請設計一個高效算法，找到字符串的最長無重復字符的子串長度。

給定一個字符串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;
}

以上就是字符串的最長無重復字符的子串長度是什么，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。