All Tracks Data Structures Advanced Data Structures Suffix Arrays Problem

And it boils down to THIS!
Tag(s):

Medium

Problem
Editorial
Analytics

You have entered the last level of a very interesting game.
You win this, and you will emerge out to be the winner.

You are provided a string S, and an integer K.
You need to split the given string into atmost K contiguous parts.
For each part that emerges from the splits formed, you can either choose to follow the original order of characters , or you may reverse that part.

Your ultimate goal is to find out the lexicographically smallest string out of all the possible strings that can be formed following the above mentioned conditions.

Input
First line comprises T- the number of test cases.
T lines follow.
Each of these T lines has a string S , and an integer K.

Output
For each of the test case, output the lexicographically smallest string as described above.

Constraints
1<=T<=100000
Summation of strings over all test cases <= 1000000

Setter - Shivam Garg

SAMPLE INPUT
1
foh 1
SAMPLE OUTPUT
fho
Explanation

For the given test case, you have string foh.
You can only perform atmost one split.
If you decide to make no split at all, we have 2 choices.
Choose the original order - foh or reverse it - hof.

If you decide to make 1 split, you have these options -
f | oh -> Either take original sequence foh, or reverse the first part and get foh, or reverse the second part and get fho, or reverse both parts and get fho.
fo | h -> Either take original sequence foh, or reverse the first part and get ofh, or reverse the second part and get foh, or reverse both parts and get ofh.

Out of all possible strings, fho is lexicographically smallest.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?