[LeetCode] - Longest Substring Without Repeating Characters

發表於   |  

Question:
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.

找到字串中的子字串中有不重複的字元的最大長度，這邊提供一種方法

使用兩個指標計算長度

先以圖示的方式稍微解說一下概念，首先宣告兩個指標皆指向字串的開頭

接著ptr1指標一次一個字元向右移，一直到指到的字元是之前出現過的字元，下圖藍色區段即為第一個substring長度為5

接著ptr2移動到重覆字元位址後一個位址，找尋下一個沒有重覆字元的substring

此時ptr1前進一個且看到重複的字元，但這會造成ptr2往前面的位址移動，顯然移動後的substring會有重覆字元，因此如果ptr2移動的結果是往前面的位址移動，就不移動

依照這個規則ptr1在移動到下圖位址時會看到重覆字元，因此再找到第二個substring長度為5，ptr2也移動到第一個d後面的位址(剛好也是d)

最終ptr1和ptr2的位址如下圖，而這也是最後一個substring長度為2，因此此例最長的substring長度為5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define MAX_NUM(x, y)	(((x) >= (y)) ? (x) : (y))

#define ASCAII_CHAR_NUM			128
#define CHAR_UNUSED_FLAG		-1

int lengthOfLongestSubstring(char* s) {
	char *ptr1, *ptr2;
	int char_offset[ASCAII_CHAR_NUM]; //(1)
	int i, max_len = 0;
	int str_len = strlen(s);

	if (str_len == 0)
		return 0;

	for (i = 0; i < ASCAII_CHAR_NUM; i++)
		char_offset[i] = CHAR_UNUSED_FLAG;

	ptr1 = s; //(2)
	ptr2 = ptr1;

	for (i = 0; i < str_len - 1; i++) {
		char_offset[*ptr1] = i;
		ptr1++;
		if (char_offset[*ptr1] != CHAR_UNUSED_FLAG) { //(3)
			if (s + char_offset[*ptr1] >= ptr2) { //(4)			
				max_len = MAX_NUM(max_len, ptr1 - ptr2); //(5)
				ptr2 = s + char_offset[*ptr1];
				ptr2++; //(6)
			}
		}	
	}

	max_len = MAX_NUM(max_len, ptr1 - ptr2 + 1); //(7)
	
	return max_len;
}

(1)紀錄曾經出現過的字元的offset的table，若從未出現過則是-1

(2)ptr1及ptr2接指到字串的頭

(3)如果table不為-1代表曾經出現過此字元

(4)如果ptr2移動之後不會造成往前面的位址移動才作處理

(5)只記錄最大長度的substring，這邊要注意的是ptr1 - ptr2之所以可以等於字元的個數是因為一個字元的大小剛好為1，原本的算式為(ptr1 - ptr2) / sizof(char)，而sizeof(char)恆為1因此在這裡可以省略

(6)ptr2移動到重覆字元位址的後一個

(7)計算最後一個substring是否為最長

放到leet code上執行的結果為18ms，超過86.08%的上傳程式