Reverse Shuffle Merge


Problem Statement :


Given a string, A, we define some operations on the string as follows:

a.  denotes the string obtained by reversing string . Example: 


b.  denotes any string that's a permutation of string . Example: 


c.  denotes any string that's obtained by interspersing the two strings  & , maintaining the order of characters in both. For example,  & , one possible result of  could be , another could be , another could be  and so on.

Given a string  such that  for some string , find the lexicographically smallest .

For example, s = abab. We can split it into two strings of ab. The reverse is ba  and we need to find a string to shuffle in to get abab . The middle two characters match our reverse string, leaving the a and  b at the ends. Our shuffle string needs to be ab . Lexicographically ab < ba , so our answer is ab.

Function Description

Complete the reverseShuffleMerge function in the editor below. It must return the lexicographically smallest string fitting the criteria.

reverseShuffleMerge has the following parameter(s):

s: a string
Input Format

A single line containing the string s.


Constraints

s contains only lower-case English letters, ascii[a-z]
1  <=  | s |  <=  10000


Output Format

Find and return the string which is the lexicographically smallest valid A.



Solution :



title-img


                            Solution in C :

In  C :




#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    char s[10000],c[5000];
    int a[26],b[26],i=0,len,pos,limit,j,index;
    scanf("%s",s);
    len=strlen(s);
    pos=len-1;
    limit=len>>1;
    while(s[i])
        	a[s[i++]-97]++;
    for(i=0;i<26;i++)
        	b[i]=a[i]/2;
    for(i=0;i<limit;i++)
        {
        char best;
        int x=0;
        for(j=pos;j>=0;j--)
            {
            if((!x||s[j]<best)&&b[s[j]-97])
                {
                x=1;
                best=s[j];
                index=j;    
            }
            a[s[j]-97]--;
            if(a[s[j]-97]<b[s[j]-97])
                break;
        }
        for(; j < index; ++j)
        {
            ++a[s[j]-97];
        }
        c[i]=best;
        b[best-97]--;
        pos=index-1;
    }
    printf("%s",c);
    return 0;
}
                        


                        Solution in C++ :

In  C++  :






#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;

const int MAXN = 10000;
int cnt[26][MAXN+1];
int nxt[MAXN][26];
int shuffcnt[26];
int Acnt[26];
int totals[26];
int main() {
    string S;
    cin >> S;
    int n = S.size();
    assert(n%2 == 0);
    reverse(S.begin(), S.end());
    for (int i=0; i<n; ++i) {
        for (int j=0; j<26; ++j) {
            cnt[j][i+1] = cnt[j][i];
        }
        ++cnt[S[i]-'a'][i+1];
    }
    for (int j=0; j<26; ++j) {
        nxt[n-1][j] = -1;
    }
    nxt[n-1][S[n-1]-'a'] = n-1;
    for (int i=n-2; i>=0; --i) {
        for (int j=0; j<26; ++j) {
            nxt[i][j] = nxt[i+1][j];
        }
        nxt[i][S[i]-'a'] = i;
    }

    for (int c=0; c<26; ++c) {
        assert(cnt[c][n]%2 == 0);
        totals[c] = cnt[c][n]/2;
    }

    string sol;
    int start = 0;
    while ((int)sol.size() < n/2) {
        assert(start < n);
        for (int c=0; c<26; ++c) {
            if (Acnt[c] == totals[c]) continue;
            int p = nxt[start][c];
            if (p == -1) continue;
            bool ok = true;
            for (int j=0; j<26; ++j) {
                if (shuffcnt[j]+(cnt[j][p]-cnt[j][start]) > totals[j]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                sol += char(c + 'a');
                for (int j=0; j<26; ++j) {
                    shuffcnt[j] += cnt[j][p] - cnt[j][start];   
                }
                ++Acnt[c];
                start = p + 1;
                break;
            }
        }
    }
    assert(int(sol.size()) == n/2);
    cout << sol << '\n';
    vector<int> tst(26);
    for (int i=0; i<(int)sol.size(); ++i) {
        ++tst[sol[i]-'a'];
    }
    for (int j=0; j<26; ++j) {
        assert(tst[j] == totals[j]);
    }
    return 0;
}
                    


                        Solution in Java :

In   Java :





import java.io.*;
import java.util.*;
import java.math.*;

public class Solution implements Runnable {
	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer st;
	static Random rnd;

	private void solve() throws IOException {
		int tests = 1;
		for (int test = 0; test < tests; test++)
			solveOne();
	}

	private void solveOne() throws IOException {
		String s = nextToken();
		s = reverseString(s);
		final int alphaSize = 26;
		int[] count = new int[alphaSize];
		for (int i = 0; i < s.length(); i++)
			++count[s.charAt(i) - 'a'];
		int needLength = 0;
		for (int i = 0; i < alphaSize; i++) {
			if (count[i] % 2 != 0)
				throw new AssertionError();
			count[i] /= 2;
			needLength += count[i];
		}
		StringBuilder result = new StringBuilder();
		int[][] counts = new int[s.length()][alphaSize];
		for (int i = s.length() - 1; i >= 0; i--) {
			for (int j = 0; j < alphaSize; j++)
				counts[i][j] = (i + 1 == s.length() ? 0 : counts[i + 1][j]);
			counts[i][s.charAt(i) - 'a']++;
		}
		int leftPointer = 0;
		for (int it = 0; it < needLength; it++) {
			int resultIndex = -1;
			for (int i = leftPointer; i < s.length(); i++) {
				// out.println(it + " " + i + " " + resultIndex);
				if (count[s.charAt(i) - 'a'] > 0) {
					if (resultIndex == -1
							|| s.charAt(i) < s.charAt(resultIndex)) {
						if (isOk(count, counts[i]))
							resultIndex = i;
					}
				}
			}
			result.append(s.charAt(resultIndex));
			--count[s.charAt(resultIndex) - 'a'];
			leftPointer = resultIndex + 1;
			// out.println(resultIndex + " " + result);
			// out.flush();
		}
		out.println(result);
	}

	private boolean isOk(int[] a, int[] b) {
		for (int i = 0; i < a.length; i++)
			if (a[i] > b[i])
				return false;

		return true;
	}

	private String reverseString(String s) {
		return new StringBuilder(s).reverse().toString();
	}

	public static void main(String[] args) {
		new Solution().run();
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			rnd = new Random();

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	private String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = in.readLine();

			if (line == null)
				return null;

			st = new StringTokenizer(line);
		}

		return st.nextToken();
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}
                    


                        Solution in Python : 
                            
In Python3 :





from collections import defaultdict
S = input()
S = S[::-1]
count = defaultdict(int)
for c in S:
    count[c] += 1
need = {}
for c in count:
    need[c] = count[c] / 2
solution = []
i = 0
while len(solution) < len(S) / 2:
    min_char_at = -1
    while True:
        c = S[i]
        if need[c] > 0 and (min_char_at < 0 or c < S[min_char_at]):
            min_char_at = i
        count[c] -= 1
        if count[c] < need[c]:
            break
        i += 1
    for j in range(min_char_at+1, i+1):
        count[S[j]] += 1
    need[S[min_char_at]] -= 1
    solution.append(S[min_char_at])
    i = min_char_at + 1
print(''.join(solution))
                    


View More Similar Problems

Kindergarten Adventures

Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti

View Solution →

Mr. X and His Shots

A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M

View Solution →

Jim and the Skyscrapers

Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space

View Solution →

Palindromic Subsets

Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t

View Solution →

Counting On a Tree

Taylor loves trees, and this new challenge has him stumped! Consider a tree, t, consisting of n nodes. Each node is numbered from 1 to n, and each node i has an integer, ci, attached to it. A query on tree t takes the form w x y z. To process a query, you must print the count of ordered pairs of integers ( i , j ) such that the following four conditions are all satisfied: the path from n

View Solution →

Polynomial Division

Consider a sequence, c0, c1, . . . , cn-1 , and a polynomial of degree 1 defined as Q(x ) = a * x + b. You must perform q queries on the sequence, where each query is one of the following two types: 1 i x: Replace ci with x. 2 l r: Consider the polynomial and determine whether is divisible by over the field , where . In other words, check if there exists a polynomial with integer coefficie

View Solution →