leetcode系列(双语)003——GO无重复字符的最长子串

003、Longest Substring Without Repeating Characters

无重复字符的最长子串

Given a string s, find the length of the longest substring without repeating characters.

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

Example :
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

示例:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

个人解题

func lengthOfLongestSubstring(s string) int {
	m := make(map[uint8]int)
	//记录当前字符的长度
	strLen := 0
	//记录最大的字符的长度
	maxStrLen := 0
	//计算字符的长度的开始下标
	start := 0

	for i := 0; i < len(s); i++ {
		//查询判断m是否存在字符
		temp := m[s[i]]
		if temp == 0 {
			//不存在，保存记录
			m[s[i]] = 1
			//当前长度+1
			strLen++
		} else {
			//存在重复字符串
			//判断当前长度是否超过最大长度
			if strLen > maxStrLen {
				maxStrLen = strLen
			}
			//重置
			strLen = 0
			if start < len(s) {
				i = start
				m = make(map[uint8]int)
			} else {
				break
			}
			start++
		}
	}
	//判断当前长度是否超过最大长度
	if strLen > maxStrLen {
		maxStrLen = strLen
	}
	return maxStrLen
}
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
37
38
39
40

官方解题

func lengthOfLongestSubstring(s string) int {
    // 哈希集合，记录每个字符是否出现过
    m := map[byte]int{}
    n := len(s)
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    rk, ans := -1, 0
    for i := 0; i < n; i++ {
        if i != 0 {
            // 左指针向右移动一格，移除一个字符
            delete(m, s[i-1])
        }
        for rk + 1 < n && m[s[rk+1]] == 0 {
            // 不断地移动右指针
            m[s[rk+1]]++
            rk++
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i + 1)
    }
    return ans
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}
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

扩展

Given a string, print the longest substring without repeating characters in Golang. For example, the longest substrings without repeating characters for “ABDEFGABEF” are “BDEFGA”.

Examples:

Input : GEEKSFORGEEKS
Output :
Substring: EKSFORG
Length: 7

Input : ABDEFGABEF
Output :
Substring: BDEFGA
Length: 6
The idea is to traverse the string and for each already visited character store its last occurrence in an array pos of integers(we will update the indexes in the array based on the ASCII values of the characters of the string). The variable st stores starting point of current substring, maxlen stores length of maximum length substring, and start stores starting index of maximum length substring.

While traversing the string, check whether the current character is already present in the string by checking out the array pos. If it is not present, then store the current character’s index in the array with value as the current index. If it is already present in the array, this means the current character could repeat in the current substring. For this, check if the previous occurrence of character is before or after the starting point st of the current substring. If it is before st, then only update the value in array. If it is after st, then find the length of current substring currlen as i-st, where i is current index.

Compare currlen with maxlen. If maxlen is less than currlen, then update maxlen as currlen and start as st. After complete traversal of string, the required longest substring without repeating characters is from s[start] to s[start+maxlen-1].

// Golang program to find the length of the
// longest substring without repeating
// characters

package main

import “fmt”

func longest_substring(s string, n int) string {

var i int
  
// starting point of 
// current substring. 
st := 0     
  
// length of current substring.   
currlen := 0  
  
// maximum length substring  
// without repeating  characters 
maxlen := 0   

// starting index of  
// maximum length substring. 
start := 0 

// this array works as the hash table 
// -1 indicates that element is not 
// present before else any value  
// indicates its previous index 
pos := make([]int, 125) 

for i = 0; i < 125; i++ { 

    pos[i] = -1 
} 

// storing the index 
// of first character 
pos[s[0]] = 0 

for i = 1; i < n; i++ { 

    // If this character is not present in array, 
    // then this is first occurrence of this 
    // character, store this in array. 
    if pos[s[i]] == -1 { 
        pos[s[i]] = i 
    } else { 
      
        // If this character is present in hash then 
        // this character has previous occurrence, 
        // check if that occurrence is before or after 
        // starting point of current substring. 
        if pos[s[i]] >= st { 

            // find length of current substring and 
            // update maxlen and start accordingly. 
            currlen = i - st 
            if maxlen < currlen { 

                maxlen = currlen 
                start = st 
            } 
            // Next substring will start after the last 
            // occurrence of current character to avoid 
            // its repetition. 

            st = pos[s[i]] + 1 

        } 
        // Update last occurrence of 
        // current character. 
        pos[s[i]] = i 
    } 

} 
// Compare length of last substring  
// with maxlen and update maxlen  
// and start accordingly. 
if maxlen < i-st { 

    maxlen = i - st 
    start = st 
} 
  
// the required string 
ans := ""

// extracting the string from  
// [start] to [start+maxlen] 
for i = start; i < start+maxlen; i++ { 
    ans += string(s[i]) 
} 

return ans 
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

}

func main() {

var s string = "GEEKSFORGEEKS"
var n int = len(s) 

// calling the function to  
// get the required answer. 
var newString = longest_substring(s, n) 
  
// finding the length of the string 
var length int = len(newString) 

fmt.Println("Longest substring is: ", newString) 
fmt.Println("Length of the string: ", length) 
1
2
3
4
5
6
7
8
9
10
11
12

}
Output:

Longest substring is: EKSFORG
Length of the string: 7
Note: Instead of using the array, we can also use a map of string to int.

Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, GeeksforGeeks Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out - check it out now!