寻找最小子字符串

class Solution:
    def getMinString(self , str1 , str2 ):
        # write code here
        if not str2:return str1
        minindex = len(str2)
        maxindex = 0
        flag = 0
        str3 = list(str1).copy()
        for i in str2:
            if i in str3:
                flag += 1
                minindex = min(str3.index(i),minindex)
                maxindex = max(str3.index(i),maxindex)
                str3[str3.index(i)] = " "
        return str1[minindex:maxindex+1]if flag == len(str2) else ""

class Solution:
    def getMinString(self , str1 , str2 ):
        # write code here
        str1l=list(str1)
        str2l=list(str2)
        if len(str2)==0:
            return str1
        tmp1=str1l.copy()
        p=[]
        for i in range(len(str2)):
            x=0
            for j in range(len(str1)):
                if tmp1[j]==str2l[i]:
                    p.append(j)
                    tmp1[j]=" "
                    x=1
                    break
            if x==0:
                return ""
        return(str1[min(p):max(p)+1])

public String getMinString (String str1, String str2) {
        // write code here
        if(str2==null||str2.length()==0){ return str1;}
        int[] strA = new int[128];
        int[] strB = new int[128];
        int left = 0,right = 0;
        for(int i=0;i<str1.length();i++){
            strA[str1.charAt(i)]++;
        }
        for(int i=0;i<str2.length();i++){
            strB[str2.charAt(i)]++;
        }
        // 没有完全包含所有字符,str2中有个字符多了几个或一个。
        for(int k=0;k<str2.length();k++){//str.charAt()
            if(strA[str2.charAt(k)]<strB[str2.charAt(k)]){
                return "";
            }
        }
        //find left
        for(int k=0;k<str1.length();k++){
            //保证相同数目的字符在范围内
            if(--strA[str1.charAt(k)]<strB[str1.charAt(k)]){
                left=k;
                break;
            }
        }
        for(int k=str1.length()-1;k>=0;k--){
            if(--strA[str1.charAt(k)]<strB[str1.charAt(k)]){
                right=k;
                break;
            }
        }

        return str1.substring(left,right+1);
    }

1.     自己构建hash函数表，记录每个单词出现的次数。

2.     找出特殊情况，str2中某个字符的数量，少于str1中。

3.     找出left,与right

str1=aaabbc    str2=aab     [--3<2 index=0]    [--2<2 index=1=left]

str1=abbcd      str2=bbc    [--1<0 index=0]    [--2<2 index=1=left ]

left满足 str1当前字符在str2中，并且str1当前字符在右边的数量小于当前字符在str2中的数量.  即--strA[ str1.charAt(k) ]<strB[ str1.charAt(k) ]

class Solution:
    def getMinString(self, str1, str2):
        if str2:
            index_list = []
            for letter in str2:
                _index = str1.find(letter)
                if _index in index_list:
                    _index = str1.find(letter, _index + 1)
                index_list.append(_index)
            result = str1[min(index_list):max(index_list) + 1]
            if -1 in index_list:
                result = ""
        else:
            result = str1
        print(result)

class Solution:
    def getMinString(self , str1 , str2 ):
        # write code here
        if not str2:
            return str1
        dic = {}
        for char in str2:
            dic[char] = dic.get(char, 0) + 1
        indexes = []
        for key, value in dic.items():
            if str1.count(key) < value:
                return ''
            index_ = -1
            for _ in range(value):
                index_ = str1.index(key, index_+1)
            indexes.append(index_)
        return str1[min(indexes):max(indexes) + 1]

import re from functools import reduce def list_combination(lists,code=''): def myfunc(list1, list2): return [str(i) + code + str(j) for i in list1 for j in list2] return reduce(myfunc, lists)
n = []
str_temp = str1 = input()
str2 = input()
a = 0 for i in str2: if i in str_temp:
        a += 1  str_temp = str_temp.replace(i, '') if str2 == '': print(str1) elif len(str2) > a: print(' ') else: for i in str2:
        m = [] for h in re.finditer(i, str1):
            x = h.start()
            m.append(x)
        n.append(m) # print(n)  # print('常见写法结果：\n', list_combination(n, '+'))  # 排列结果用+连接  result = list_combination(n, '+') # print(result)  res = [] for i in result:
        temp = list(map(int,i.split('+')))
        a = max(temp) - min(temp) + 1  b = [a,i]
        res.append(b) print(res)
    x = int(res[0][0])
    y = res[0][1] for i in res: if int(i[0]) < x:
            x = i[0]
            y = i[1] # print(y)  temp = list(map(int, y.split('+')))
    a = max(temp) + 1  b = min(temp) print(str1[b:a])

def minwindow(s1,s2):
    if s2 is None:
        return s1
    need,window=defaultdict(int),defaultdict(int)
    left,right,vaild=0,0,0
    start,curlen=0,float('inf')
    for i in s2:
        need[i]+=1
    while right<len(s1):
        c=s1[right]
        right+=1
        if c in s2:
            window[c]+=1
            if window[c]==need[c]:
                vaild+=1
        while vaild==len(need):
            if right-left<curlen:
                curlen=right-left
                start=left
            d=s1[left]
            left+=1
            if d in s2:
                if need[d]==window[d]:
                    vaild-=1
                window[d]-=1
    if curlen==float('inf'):
        return ""
    else:
        return s1[start:start+curlen] 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int inStr(char c, char *str) {
    char *p = str;
    int i = 0;
    while('\0' != *p) {
        if (*p == c) {
            return i;
        }
        p ++;
        i ++;
    }
    return -1;
}

void printSubStr(char *str, int start, int end) {
    char *p = str;
    for (int i = start; i <= end; i ++) {
		printf("%c", str[i]);
    }
}

int findMinSubStr(char *s, char *t, int *start, int *end) {
    
    char *sp = s;
    
    size_t sLen = strlen(s);
    size_t tLen = strlen(t);
    
    unsigned long long bitmaps[sLen];
    memset(bitmaps, 0, sizeof(unsigned long long) * sLen);
    int positions[sLen];
    int substrMap[sLen];
    int minLen = 0;
    int minPos = 0;
    
    int i = 0, k = 0;

    while ('\0' != *sp) {
        unsigned int pos = inStr(*sp, t);
        if (-1 != pos) {
//            printf("find s[%d]=%c\n", i, *sp);  // 4debug
            positions[k] = i;
            for (int j = 0; j <= k; j ++) {
                if (substrMap[positions[j]] > 0) {	// already find a Min-Length-Substr started from j
//                    printSubStr(s, positions[j], substrMap[positions[j]]); printf(" is already a substr!\n"); // 4debug
                    continue;
                }
            	bitmaps[positions[j]] |= (1 << pos);	// update every bitmap
                if (bitmaps[positions[j]] == (1 << tLen) - 1) {	// find a substr
                    substrMap[positions[j]] = i;	// recode this Min-Length-Substr end position by start position indexing
                    if (i - positions[j]+ 1 < minLen || minLen == 0) {
                        minPos = positions[j];	// update Min-Length-Substr start position
                        minLen = i - positions[j]+ 1;	// update min length
                    }
//                    printSubStr(s, positions[j], i); printf(" is a new substr! (minPos=%d, minLen=%d)\n", minPos, minLen); // 4debug
                }
            }
            k ++;
//            printf("\n");   // 4debug
        }
        sp ++, i ++;
    }
    if (minLen == 0) {
	    return -1;
    }
    *start = minPos;
    *end = substrMap[minPos];
    return 0;
}

int main() {
    char s[1024], t[64];
    scanf("%s\n%s", s, t);
    int start, end;
    if (0 == findMinSubStr(s, t, &start, &end)) {
    	printSubStr(s, start, end);
    }
    printf("\n");
    return 0;
}

#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return string字符串
#
class Solution:
    def getMinString(self , str1 , str2 ):
        # write code here
        if str2 == "":
            return str1
        elif len(str2) > len(str1):
            return ""
        results = []
        result = []
        ls = []
        str2t = str2
        i = 0
        append = False
        while i < len(str1):
            if str1[i] in str2t:
                append = True
                str2t = str2t.replace(str1[i], "", 1)
                if str2t == "":
                    result.append(str1[i])
                    results.append(result)
                    ls.append(len(result))
                    str2t = str2
                    result = []
                    append = False
            if append:
                result.append(str1[i])
            i += 1
        if len(results) == 0:
            return ""
        else:
            minl = min(ls)
            for i in results:
                if len(i) == minl:
                    return "".join(i)

import java.util.*;


public class Solution {
    /**
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return string字符串
     */
    public String getMinString (String str1, String str2) {
       // write code here
        if(str2.length() == 0) return  str1;
        int[] map = new int[128];
        for (char c : str2.toCharArray())
            map[c]++;
        int counter = str2.length(),begin = 0,end = 0,distance = Integer.MAX_VALUE,head = 0;
        while(end<str1.length()){
            if(map[str1.charAt(end++)]-- >0)counter -- ;
            while(counter==0){
                if(end - begin<distance) distance = end-(head =begin);
                if(map[str1.charAt(begin++)]++ == 0) counter++;
            }
        }
        return distance == Integer.MAX_VALUE ? "" : str1.substring(head, head + distance);
        
    }
}

# python
input_str = input()

father_str = input_str.split(",")[0].split("\"")[1]
son_str = input_str.split(",")[1].split("\"")[1]

result = ""
index_list = []

for letter in son_str:
    _index = father_str.find(letter)
    if _index in index_list:
        _index = father_str.find(letter, _index+1)
    index_list.append(_index)

if len(index_list) == 0:
    result = father_str
else:
    result = father_str[min(index_list):max(index_list)+1]

if -1 in index_list:
    result = ""

print("\""+result+"\"")