class Result {

static char[] position;
static int[] count;
static int n;
static int m;
static HashMap<Integer, int[]> right;
static HashMap<Integer, List<Integer>> myMap;
static int min;

public static String reverseShuffleMerge(String s) {
    n = s.length();
    m = n / 2;
    String ss = new StringBuilder(s).reverse().toString();
    count = new int[26];
    right = new HashMap<>();
    myMap = new HashMap<>();
    for (int i = n - 1; i >= 0; i--) {
        int[] temp = Arrays.copyOf(count, 26);
        right.put(i, temp);
        count[ss.charAt(i) - 'a']++;
        int value = ss.charAt(n - 1 - i) - 'a';
        List<Integer> tempList = myMap.getOrDefault(value, new ArrayList<Integer>());
        tempList.add(n - 1 - i);
        myMap.put(value, tempList);
    }

    for (int i = 0; i < 26; i++) count[i] /= 2;
    min = -1;
    position = new char[m];

    for (int i = 0; i < m; i++) {
        labelA:
        for (int j = 0; j < 26; j++) {
            if (count[j] == 0) continue;
            List<Integer> tempL = myMap.get(j);
            for (int k = 0; k < tempL.size(); k++) {
                if (tempL.get(k) <= min) continue;
                count[j]--;
                if (isValid(tempL.get(k))) {
                    min = tempL.get(k);
                    position[i] = (char)('a' + j);
                    break labelA;
                }else{
                    count[j]++;
                    break;
                }
            }
        }
    }
    return new String(position);   
// Write your code here
}

static boolean isValid(int p) {
    int[] temp = right.get(p);
    for (int i = 0; i < 26; i++) {
        if (temp[i] < count[i]) return false;
    }
    return true;
}

}

for str = abcdefgabcdefg why cant the ans be abcdefg ?

A simple and easy to understand explanation:

https://youtu.be/_QQe2TQ2o_4?t=354

A very easy to understand example is available in this video.

https://youtu.be/_QQe2TQ2o_4?t=354

The explanation helped me understand the algorithm on how we can solve the problem.

Simple C++ Solution

Approach: As we want Lexicographically smallest possible A, we will try take smaller char first if posiible. Each char to be taken must have freq = half of freq in given string s. Now as original A is in reverse order in given string so traverse the string s from last.

• store count of each char in unused[] array
• store required count for each char in A in required[] array which = half of count of char in unused[] array
• take taken array initialize to 0

Now for each char ch in s:
    if(taken[ch] < required[ch]) do
        lci = last char inserted
        if(ch > lci) then push ch and taken[ch]++
        else{
            if(lci > ch and available count for lci (if we delete it) >= required[ch])
                pop lci and taken[ch]--;
            At last push ch and taken[ch]++;
        }
        mark ch as used
        unused[ch]--;
				

 string reverseShuffleMerge(string s) {
int taken[26] = {0}, required[26] = {0}, unused[26] = {0};
for(auto ch: s)
    unused[ch - 'a']++;
for(auto ch: s)
    required[ch - 'a'] = unused[ch - 'a'] >> 1;
stack<char>st;
for(int i = s.length()-1; i >= 0; i--){
    char ch = s[i];
    int pos = ch - 'a';
    if(taken[pos] < required[pos]){
        if(st.empty()){
            st.push(ch);
            taken[pos]++;
        }
        else if(st.top() - ch < 0){
            st.push(ch);
            taken[pos]++;
        }
        else{
            while(!st.empty() and st.top() - ch >0 and unused[st.top()-'a'] >= required[st.top()-'a']-(taken[st.top()-'a']-1)){
                taken[st.top()-'a']--;
                st.pop();
            }
            st.push(ch);
            taken[pos]++;
        }
    }
    unused[pos]--;
}
string ans = "";
while(!st.empty()){
    ans = st.top() + ans;
    st.pop();
}
return ans;

}

}
return ans;