We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Greedy
  4. Reverse Shuffle Merge

Reverse Shuffle Merge

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Given a string, , 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, . We can split it into two strings of . The reverse is and we need to find a string to shuffle in to get . The middle two characters match our reverse string, leaving the and at the ends. Our shuffle string needs to be . Lexicographically , so our answer is .

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 .

Constraints

  • contains only lower-case English letters, ascii[a-z]

Output Format

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

Sample Input 0

eggegg

Sample Output 0

egg

Explanation 0

Split "eggegg" into strings of like character counts: "egg", "egg"
reverse("egg") = "gge"
shuffle("egg") can be "egg"
"eggegg" belongs to the merge of ("gge", "egg")

The merge is: gge.

'egg' < 'gge'

Sample Input 1

abcdefgabcdefg

Sample Output 1

agfedcb

Explanation 1

Split the string into two strings with like characters: and .
Reverse =
Shuffle can be
Merge to bcdefga

Sample Input 2

aeiouuoiea

Sample Output 2

aeiou

Explanation 2

Split the string into groups of like characters:
Reverse =
These merge to uoiea

Author

wanbo

Difficulty

Advanced

Max Score

50

Submitted By

16216

Need Help?


View discussions
View editorial
View top submissions
RESOURCES

  • String Basics
  • Greedy Technique

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature