今天開始來研究 String 相關的問題
這次的題目是要找出一個字串中沒有重複字元的最長子字串的長度

問題

https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

Example 1:

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

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

提示

如何檢查一個 key 已經在 hash table 中

Python

if key1 in hashmap:
  // do sothing

Go

// If a key doesn't exist in the map, we get the zero value of the value type
fmt.Println("Salad's price is", m["Salad"])

// Appropriate way to check key exist or not
price, priceExist := m["Salad"]
if priceExist {
    fmt.Println("Salad's price is", price)
} else {
    fmt.Println("This store does not sell Salad")
}

Go 沒有 'Char' 資料格式

Go 沒有 'Char' 資料格式．
他使用 byte/uint8 跟 rune/int32 格式來存 character 資料值.

helloStr := "Hello World!"

fmt.Printf("type of helloStr[0] is %T\n", helloStr[0])
// type of helloStr[0] is uint8

我的答案

用兩個指標（ left 跟 right ）來表示目前所見的沒有重複字元的子字串．

Case 1: 遇見重複的字元(d)，且前重複的字元在目前的子字串內，則移動 left 指標．
Case 2: 遇見重複的字元(a)，但前重複的字元不在目前的子字串內，則乎略它．

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hashmap = {}
        ans, left = 0, 0
        for right in range(len(s)):
            """
            We need to cange the left pointer only when there is duplicate element and the previous duplcated element was in current substring.
            """
            if s[right] in hashmap and hashmap[s[right]] >= left:
                left = hashmap[s[right]] + 1
            else:
                ans = max(ans, right - left + 1)
            hashmap[s[right]] = right
        return ans

Go

import "math"
func lengthOfLongestSubstring(s string) int {
    hashmap := map[byte]int{}
    ans := 0
    left := 0
    for right := 0; right < len(s) ; right++ {
        repeatCharIndex, repeatCharExist := hashmap[s[right]]
        if repeatCharExist && repeatCharIndex >= left {
            left = repeatCharIndex + 1
        } else {
            ans = int(math.Max(float64(ans), float64(right - left + 1)))
        }
        hashmap[s[right]] = right   
    }
    return ans  
}