給定兩個(gè)字符串string1和string2。

string1是一個(gè)被加擾的字符串。string1由小寫英文字母('a'~'z')和數(shù)字字符('0'~'9')組成，而加擾字符串由'0'~'9'、'a'~'f'組成。string1里面可能包含0個(gè)或多個(gè)加擾子串，剩下可能有0個(gè)或多個(gè)有效子串，這些有效子串被加擾子串隔開。

string2是一個(gè)參考字符串，僅由小寫英文字母('a'~'z')組成。

你需要在string1字符串里找到一個(gè)有效子串，這個(gè)有效子串要同時(shí)滿足下面兩個(gè)條件:

(1)這個(gè)有效子串里不同字母的數(shù)量不超過且最接近于string2里不同字母的數(shù)量，即小于或等于string2里不同字母的數(shù)量的同時(shí)且最大。

(2)這個(gè)有效子串是滿足條件(1)里的所有子串(如果有多個(gè)的話)里字典序，最大的一個(gè)。

如果沒有找到合適條件的子串的話，請輸出"Not Found"

示例:

輸入字符串string1為"thisisanewday111forme"，輸入字符串string2為"good"。

string1里有效子串和加擾子串分割后可表示為:"thisis"+"a"+"n"+"e"+"w"+"da"+"y"+"111f"+"orm"+"e"，去除加擾子串("a"、"e"、"da"、"111f"、"e")后的有效子串候選為("thisis"，"n"，"w""y"，"orm")。

輸入字符串string2里不同字母的數(shù)量為3('g'、'o'、'd')，從有效子串候選里可以找出"orm"滿足要求，其不同字母的數(shù)量為3，最接近于string2不同字母的數(shù)量。

輸入描述:

input_string1 input_string2

說明:輸入為兩個(gè)字符串，第1行是題目里的string1(被加擾的字符串)，第2行是題目里的strinq2(參考字符串)

輸出描述:

output_string

說明:輸出為一個(gè)字符串(有效字符串)補(bǔ)充說明:

輸入字符串string1的長度在1~100000之間，string2的長度在1~500之間

示例1

輸入:

123admyffc79pt

ssyy

輸出:

pt

說明:

將輸入字符串1里的加擾子串"123ad"、"ffc79"去除后得到有效子串序列:"my"、"pt"，其中"my"里不同字母的數(shù)量為2(有'm'和'y'兩個(gè)不同字母)，"pt"里不同字母的數(shù)量為2(有'p'和't'兩個(gè)不同字母);輸入字符串2里不同字母的數(shù)量為2(有's'和'y'兩個(gè)不同字母)。

可得到最終輸出結(jié)果為"pt"，其不同字母的數(shù)量最接近于"ssy"里不同字母的數(shù)量的同時(shí)字典序最大。

示例2

輸入:

123admyffc79ptaagghi2222smeersst88mnrt

ssyyfgh

輸出:

mnrt

說明:

將輸入字符串1里的加擾子串"123ad"，"ffc79"，"aa"，"2222"，"ee"，"88"去除后得到有效子串序列:"mv"、"pt"、"aahi"、"sm"."rsst""mnrt":輸入字符串2里不同字母的數(shù)量 5(有's'、'v''f、'a'、'h'5個(gè)不同字母)?？傻玫阶罱K輸出結(jié)果為"mnrt"，其不同字母的數(shù)量(為4)最接近干"ssvvfah"里不同字母的數(shù)量，其他有效子串不同字母的數(shù)量都小于"mnrt"。

示例3

輸入:

abcmnq

rt

輸出:

Not Found

說明:

將輸入字符串1里的加擾子串"abc"去除后得到有效子串序列:"mna":輸入字符串2里不同字母的數(shù)量為2(有”"兩個(gè)不同的字母)?？傻玫阶罱K的輸出結(jié)果為"Not Found"，沒有符合要求的有效子串，因有效子串的里不同字母的數(shù)量(為3)，大于輸入字符串2里的不同字母的數(shù)量

————————————————

版權(quán)聲明：本文為CSDN博主「MISAYAONE」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。

原文鏈接：https://renjie.blog.csdn.net/article/details/128455555

Java 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128455555

Python實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128455537

C++ 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128455527

JavaScript實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128995745

C語言版本持續(xù)更新中