Wonderland
  • README.md
  • Notebook
    • Crypto
      • Solana
        • Troubleshooting
          • BPF SDK path does not exist
    • Language
      • Rust
        • Reference
          • Capturing the Environment with Closures
          • Understanding &mut &mut Reference
      • C++
        • Reference
          • Code for MS rand() and srand() in VC++ 6.0
  • Textbook
    • Serials
      • A Real-Time Cryptocurrency Ticker Dashboard
        • 0 - Some Preparation
    • Frontend
      • A Simple Progress Bar
      • A React Ribbon Component
      • An Easy to Use React DnD Sortable Component
      • Sticky Header, Sticky Footer and Fluid Content
      • How To Set Same Height As Width In CSS
  • dictionary
    • Alphabet
      • MySQL
      • FFmpeg
    • Algorithm
      • Diary
        • 2022
          • 07
            • 2022-07-02
            • 2022-07-01
          • 06
            • 2022-06-30
            • 2022-06-29
            • 2022-06-28
            • 2022-06-27
            • 2022-06-26
            • 2022-06-25
            • 2022-06-24
            • 2022-06-23
            • 2022-06-22
            • 2022-06-21
            • 2022-06-20
            • 2022-06-19
            • 2022-06-18
            • 2022-06-17
            • 2022-06-16
            • 2022-06-15
            • 2022-06-14
            • 2022-06-13
            • 2022-06-12
            • 2022-06-11
            • 2022-06-10
            • 2022-06-09
            • 2022-06-08
            • 2022-06-07
            • 2022-06-06
            • 2022-06-05
            • 2022-06-04
            • 2022-06-03
            • 2022-06-02
            • 2022-06-01
          • 05
            • 2022-05-31
            • 2022-05-30
            • 2022-05-29
            • 2022-05-28
            • 2022-05-27
            • 2022-05-26
            • 2022-05-25
            • 2022-05-24
            • 2022-05-23
            • 2022-05-22
            • 2022-05-21
            • 2022-05-20
            • 2022-05-19
            • 2022-05-18
            • 2022-05-17
            • 2022-05-16
            • 2022-05-15
    • Troubleshooting
      • A Weird Python Command Not Found Problem
Powered by GitBook
On this page
  • 3. Longest Substring Without Repeating Characters
  • Description
  • Solution
  • 567. Permutation in String
  • Description
  • Solution
  1. dictionary
  2. Algorithm
  3. Diary
  4. 2022
  5. 05

2022-05-20

Last updated 2 years ago

Description

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 * 10^4

  • s consists of English letters, digits, symbols and spaces.

Solution

Approach #0

func lengthOfLongestSubstring(s string) (res int) {
    sList := []rune(s)

    for i := 0; i < len(sList); i++ {
        tmp := 0
        m := make(map[rune]struct{})
        for j := i; j < len(sList); j++ {
            if _, ok := m[sList[j]]; ok {
                break
            }
            m[sList[j]] = struct{}{}
            tmp++
        }
        res = max(res, tmp)
        delete(m, sList[i])
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Approach #1

Approach #1, #2 and #3 shows different process when counting the right side of the window.

func lengthOfLongestSubstring(s string) (res int) {
    m := make(map[byte]struct{})
    i, j := 0, 0
    for ; j < len(s); j++ {
        for ; i < j; i++ {
            if _, ok := m[s[j]]; !ok {
                break
            }
            delete(m, s[i])
        }
        m[s[j]] = struct{}{}
        res = max(res, j-i+1)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Approach #2

func lengthOfLongestSubstring(s string) (res int) {
    m := make(map[byte]struct{})
    i, j := 0, 0
    for j < len(s) {
        in := s[j]
        j++
        if _, ok := m[in]; ok {
            for i < j {
                out := s[i]
                i++
                if out == in {
                    break
                }
                delete(m, out)
            }
        }
        m[in] = struct{}{}
        res = max(res, j-i)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Approach #3

func lengthOfLongestSubstring(s string) (res int) {
    m := make(map[byte]int)
    i := -1
    for j := 0; j < len(s); j++ {
        in := s[j]
        if last, ok := m[in]; ok {
            i = max(last, i)
        }
        m[in] = j
        res = max(res, j-i)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Description

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

  • 1 <= s1.length, s2.length <= 10^4

  • s1 and s2 consist of lowercase English letters.

Solution

Approach #0

func checkInclusion(s1 string, s2 string) bool {
    current := make(map[byte]int)
    target := make(map[byte]int)
    for i := 0; i < len(s1); i++ {
        target[s1[i]]++
    }

    i, j := 0, 0
    valid := 0
    for j < len(s2) {
        in := s2[j]
        j++
        if _, ok := target[in]; ok {
            current[in]++
            if current[in] == target[in] {
                valid++
            }
        }

        for j-i >= len(s1) {
            if valid == len(target) {
                return true
            }
            out := s2[i]
            i++
            if _, ok := target[out]; ok {
                if current[out] == target[out] {
                    valid--
                }
                current[out]--
            }
        }
    }
    return false
}

Approach #1: Two Pointers

func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
    m := make(map[byte]int)
    for i := 0; i < len(s1); i++ {
        m[s1[i]]++
    }

    i, j := 0, 0
    for ; j < len(s2); j++ {
        m[s2[j]]--
        for m[s2[j]] < 0 {
            m[s2[i]]++
            i++
        }
        if j-i+1 == len(s1) {
            return true
        }
    }
    return false
}

3. Longest Substring Without Repeating Characters
567. Permutation in String