Given two binary strings s and t. The task is to rearrange the string s in such a way that the occurrence of string t as a sub-string in s is maximum.
Examples:
Input: s = “101101”, t = “110”
Output: 110110Input: s = “10”, t = “11100”
Output: 10Input: s = “11000100”, t = “101”
Output: 10101000
Approach: If we can not make any occurrence of string t in string s then output any permutation of s. Otherwise, start the rearranged string with t. Now we will make the next occurrence of string t in string s as left as possible in order maximize the count of occurrence. To achieve this we will find the largest suffix of string t that matches the prefix of string t
of the same length. It can be found by Prefix Function, Z-Function or Hashes.
Below is the implementation of the above approach:
# Python3 implementation of the approach from collections import defaultdict # Function to return the length of maximum # proper suffix which is also proper prefix def Prefix_Array(t): m = len(t) arr =[-1]*m k =-1 for i in range(1, m): while k>-1 and t[k + 1]!= t[i]: k = arr[k] if t[k + 1]== t[i]: k+= 1 arr[i]= k return arr[-1] # Function to return the rearranged string def Rearranged(ds, dt): check = Prefix_Array(t) # If there is no proper suffix which is # also a proper prefix if check ==-1: if ds['1']<dt['1'] or ds['0']<dt['0']: return s # If count of 1's in string t is 0 if dt['1']== 0 and ds['0']!= 0: n = ds['0']//dt['0'] temp = t * n ds['0']-= n * dt['0'] while ds['1']>0: temp+='1' ds['1']-= 1 while ds['0']>0: temp+='0' ds['0']-= 1 # Return the rearranged string return temp # If count of 0's in string t is 0 if dt['0']== 0 and ds['1']!= 0: n = ds['1']//dt['1'] temp = t * n ds['1']-= n * dt['1'] while ds['1']>0: temp+='1' ds['1']-= 1 while ds['0']>0: temp+='0' ds['0']-= 1 # Return the rearranged string return temp # If both 1's and 0's are present in # string t m1 = ds['1']//dt['1'] m2 = ds['0']//dt['0'] n = min(m1, m2) temp = t * n ds['1']-= n * dt['1'] ds['0']-= n * dt['0'] while ds['1']>0: temp+='1' ds['1']-= 1 while ds['0']>0: temp+='0' ds['0']-= 1 return temp # If there is a suffix which is # also a prefix in string t else: if ds['1']<dt['1'] or ds['0']<dt['0']: return s # Append the remaining string each time r = t[check + 1:] dr = defaultdict(int) for v in r: dr[v]+= 1 temp = t ds['1']-= dt['1'] ds['0']-= dt['0'] # If we can't form the string t # by the remaining 0's and 1's if ds['1']<dr['1'] or ds['0']<dr['0']: while ds['1']>0: temp+='1' ds['1']-= 1 while ds['0']>0: temp+='0' ds['0']-= 1 return temp # If count of 1's in string r is 0 if dr['1']== 0 and ds['0']!= 0: n = ds['0']//dr['0'] temp+= r * n ds['0']-= n * dr['0'] while ds['1']>0: temp+='1' ds['1']-= 1 while ds['0']>0: temp+='0' ds['0']-= 1 return temp # If count of 0's in string r is 0 if dr['0']== 0 and ds['1']!= 0: n = ds['1']//dr['1'] temp+= r * n ds['1']-= n * dr['1'] while ds['1']>0: temp+='1' ds['1']-= 1 while ds['0']>0: temp+='0' ds['0']-= 1 return temp # If string r have both 0's and 1's m1 = ds['1']//dr['1'] m2 = ds['0']//dr['0'] n = min(m1, m2) temp+= r * n ds['1']-= n * dr['1'] ds['0']-= n * dr['0'] while ds['1']>0: temp+='1' ds['1']-= 1 while ds['0']>0: temp+='0' ds['0']-= 1 return temp # Driver code if __name__=="__main__": s ="10101000" t ="101" # Count of 0's and 1's in string s ds = defaultdict(int) # Count of 0's and 1's in string t dt = defaultdict(int) for i in s: ds[i]= ds[i]+1 for i in t: dt[i]= dt[i]+1 print(Rearranged(ds, dt)) |
10101000
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
