Shulou(Shulou.com)06/01 Report--

This article mainly shows you "leetcode how to achieve the minimum coverage substring", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "leetcode how to achieve the minimum coverage substring" this article.

Given a string S and a string T, find the smallest string in S that contains all the letters of T.

Example:

Enter: s = "ADOBECODEBANC", T = "ABC"

Output: "BANC"

Description:

If such a substring is not stored in S, an empty string "" is returned.

If there is such a substring in S, we guarantee that it is the only answer.

Ideas for solving the problem:

1. Use hashmap to store the number of character occurrences in s and t

2. Move the right pointer. For each character in s, if it appears in t and the number of occurrences in s is not greater than that in t, it means we have found a matching character and recorded the fund.

3. If the length of found and t are the same, it means that the solution has been found.

A, containing all the characters in t

B, which contains some repetitive characters (not recorded in fund), indicating that some characters appear more frequently in s than in t

4. If the left finger aims at the frequency of the character in s greater than that in t, the character should be discarded, that is, the left pointer should be moved and the corresponding number of times should be adjusted.

5, if the number of times is equal to t, it means that we have found a local optimal solution and record it.

6, move the left pointer to the right and reduce the fund to find the next local optimal solution.

Func minWindow (s string, t string) string {src:=make (map [byte] int) dst:=make (map [byte] int) for

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.