CODEWITHSUNDEEP
pythonpython-3.xstringalgorithmsubstring
AHF
AHF

Reputation: 1072

How to find minimum substring out of string

I am trying to find the smallest substring (containing all the values of set) out of string

For example:

Input = 'xTxxOxxVxxOxVxxTxxxOxVxTxxxOxxTxVx'
Set = 'OTV'
Output = OxVxT

Input = 'UresqTcdvavUssTss'
Set = 'UT'
Output = UssT

Because OxVxT is the smallest substring (containing all the element of Set) in example-1, I have written the code for it but its not best method and not working for all examples, I am not exactly finding the smallest substrings through my code, my code is below:

def Fun(S, T):
    lst=[]
    lst1=[]
    lst2=[]
    for t in T:
        if t not in S: return False
    T = list(T)
    Z= list(T)
    C = list(T)
    for i in range(len(S)):
        if S[i] in T:
            lst.append(i)
            T.remove(S[i])
        if len(T)==0:break
    print (lst)
    U=(max(lst))
    for u in range(U+1,len(S)):
        if S[u] in Z:
            lst1.append(u)
            Z.remove(S[u])
        if len(Z)==0:break
    print (lst1)
    Q = (max(lst1))
    for u in range(Q+1,len(S)):
        if S[u] in C:
            lst2.append(u)
            C.remove(S[u])
        if len(C)==0:break
    print (lst2)
Str = 'xTxxOxxVxxOxVxxTxxxOxVxTxxxOxxTxVx'
Set = 'OTV'
Fun(Str,Set)

I am finding the all possible SubStrings indexes and then finding the distance between them and one with the shortest distance are the smallest substring in the string. My code is not working with all test cases and not giving the right result.

Upvotes: 0

Views: 347

Answers (1)

Bing Wang
Bing Wang

Reputation: 1598

this runs O(S+T), and needs python 3.7+

def Func(S,T):
    s=set(S)
    d={}
    minLen, minBegin=len(T)+1,len(T)+1
    for i,c in enumerate(T):
        if c in s:
            if c in d:
                del d[c]
            d[c]=i
            if len(d)==len(s):
                for k,v in d.items():
                    if i-v+1<minLen:
                        minLen, minBegin=i-v+1,v
                    break
    if minBegin<len(T):
        return T[minBegin:minBegin+minLen]

print(Func('UT', 'UresqTcdvavUssTss')) #Output = UssT
print(Func('OTV', 'xTxxOxxVxxOxVxxTxxxOxVxTxxxOxxTxVx')) #Output = OxVxT
print(Func('A', 'xTxxOxxVxxOxVxxTxxxOxVxTxxxOxxTxVx')) #Output = None

Upvotes: 1

Related Questions