This is the only advanced difficulty problem in the Greedy algorithms section of Hackerrank’s interview preparation kit problem set. Link here.
This problem was hard and had to get help from other users. I would like to share my thoughts.
The problem states that you are given a string s which is the result of the following operations on some string A. s = merge(reverse(A) ), shuffle(A))
The operations are defined like this:
- Merge(A, B): merges two strings into one while keeping the relative order of the characters of each string.
- Reverse(A): Reverses the string A.
- Shuffle(A): Shuffles the characters of A, or leaves them intact.
We need to find the lexicographically smallest A. Which means A with the lowest alphabetical order.
Solution
The key to this is that since Merge keeps the relative order of both strings. Our string A is hidden in-between the repeating characters in reverse order.
Pseudocode
- First we need to count the occurrences of the characters.
- Then we make a copy of the occurrences this call it the usable characters.
- Then we half the occurrences and call this the required characters
- Then we make an empty count for our solution.
- And and empty string for our solution
- From right to left in the string
s - — If the character is required
- — — we backtrack if we can and improve our solution
- — — we add the character to the solution
- — — we add it to the solution count
- — — we reduce form the usable count
- — else
- — — we ignore and reduce form the usable count
- return our solution
It should follow this logic:
s=eggeggwe iterate s right to left
- G is required We add G Sol:{g_0}
- G is required We add G Sol:{g_0, g_1}
- E is required We add E Sol:{e_0}
- we backtrack pop g_1, pop g_0
- G is required We add G Sol:{e_0, g_1}
- G is required We add G Sol:{e_0, g_1, g_2}
- E is not required Sol:{e_0, g_1, g_2}return Sol
The hard part is to know when and how many times we backtrack. This is where keeping the count of the solution and usable characters is useful. The count of the solution is how many characters will be in our solution. The usable characters count is how many characters can be used. Before backtracking we ask the question: will i be able to make the required characters if i reduce the ones i have by one taking into account the remaining to see. For instance when in the example we backtracked at E. We had 2 g’s in the solution and we were yet to see 2 g’s and the required g’s are 2. so we ask.
Will the 2 g’s i have minus one i’m about to ignore plus the ones I yet to see allow me to make the required 2 g’s? We ask the same question every time we consider backtracking.
In general we backtrack while the next character is better than the last chosen and we will be able to make up for the ignored character.
Code
static int wrd_count[26]={};
static int rem_count[26]={};
static int sol_count[26]={};
static char sol[10001];string reverseShuffleMerge(string s){
int n = s.size();
int j = 0;
const char* s_chars = s.c_str();
for(int i = 0; i < n ; i++)
wrd_count[s[i]-'a']++;
memcpy(rem_count, wrd_count,26*(sizeof(int)) );
for(int i = 0; i < 26 ; i++)
wrd_count[i]/=2;
char l_char;
int l_char_indx;
for(int i = n-1; i >= 0; i--){
l_char = s_chars[i];
l_char_indx = l_char - 'a';
if(i == n-1){
sol[j] = l_char;
j++;
rem_count[l_char_indx]--;
sol_count[l_char_indx]++;
continue;
}
if(sol_count[ l_char_indx ] < wrd_count[l_char_indx]){
if( l_char >= sol[j-1] ){
sol[j] = l_char;
j++;
rem_count[l_char_indx]--;
sol_count[l_char_indx]++;
}else{
while( j>0 && (l_char < sol[j-1]) && sol_count[sol[j-1]-'a']-1+ rem_count[sol[j-1]-'a'] >= (wrd_count[sol[j-1]-'a'])){
sol_count[sol[--j]-'a']--;
}
sol[j] = l_char;
j++;
rem_count[l_char_indx]--;
sol_count[l_char_indx]++;
}
}else{
rem_count[l_char_indx]--;
}
}
sol[j] = '\0';string sol_str(sol);
return sol_str;
}
