Leetcode - Longest Substring with At Most K Distinct Characters
https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
Given a string, find the length of the longest substring T that contains at most k distinct characters.
Example 1:
Input: s = "eceba", k = 2 Output: 3 Explanation: T is "ece" which its length is 3.
Example 2:
Input: s = "aa", k = 1 Output: 2 Explanation: T is "aa" which its length is 2.
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 | func lengthOfLongestSubstringKDistinct(s string, k int) int { if len(s) == 0 || k == 0 { return 0 } i := 0 j := i hash := map[byte]int{} max := 0 for j < len(s) { for j < len(s) { if _, ok := hash[s[j]]; !ok { if len(hash) == k { break } hash[s[j]] = j } else { hash[s[j]] = j } j++ } //fmt.Println("hash: ", hash) //fmt.Println("i, j: ", i, j) if max < j - i { max = j - i } if j >= len(s) { break } min := j minK := s[j] for key, val := range hash { if min > val { min = val minK = key } } delete(hash, minK) i = min + 1 } if j - i > max { max = j - i } return max} |
Time complexity: O(n*k)
Space complexity: O(k)
2 年前
The bank’s issued cheque is essentially a document that instructs a financial institution to pay a certain amount of money from one account to the individual whose name is printed. The individual who writes the cheque is referred to as a drawer. MICR Code on a Cheque Account holders need to keep the cash in a transaction banking account to approve it without rejection or failure.