# Rearrange given string to maximize the occurrence of string t

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:s = “101101”, t = “110”Output:110110

Input:s = “10”, t = “11100”Output:10

Input: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))` |

**Output:**

10101000