loading...
Cover image for Smallest KMP

Smallest KMP

salonix__ profile image Saloni Gupta ・2 min read

PROBLEM STATEMENT
Reorder the characters of S in such a way that P occurs in the resulting string (an anagram of S) as a substring.
Note: A string B is a substring of a string A if B can be obtained from A by deleting several (possibly none or all) characters from the beginning and several (possibly none or all) characters from the end.

Input:
akramkeeanany
aka
Output:
aaakaeekmnnry

APPROACH
Let's assume the given string be S and it's given substring be P.
Using the hashing technique, store the occurrence of both S and P in separate hashtables. Now, remove the occurrence of S's hashtable from P's hashtable. It will give all the characters apart from that present in the P string.
To make it more clear, see the code given below:

Alt Text

Now, make a new empty string "str" and append all the characters from the modified hashtable, it will give the string having characters different from those in P.

There are three orders in which we can place P in Str:
Case 1:
When P's first character is smaller than Str's first character,
here, we can place p before str.
Case 2:
When P's first character is smaller than some middle character in str, then we can P just before the character, which is strictly greater than P's first character.
Case 3:
When P's first character is the largest one, then we have to place P after str.

Another Most Important Case
When P's first character equals to some character in str, here we have two options, we can place P before that character or after that character, here we will make two string for both the cases and compare which one is larger.

CODE IMPLEMENTATION:

Alt Text

Happy Coding :)

Discussion

pic
Editor guide