HackerRank Coding Interview — String Conversion — Lexicographically Maximum Possible

Time to complete — 30minutes

Question Type = Medium

Asked in = Full stack data science, Software Engineer Technical Interview, Microsoft, Uber, Lyft, Bloomberg, Morgan Stanley, Apple, Google,

Skills: queue, strings, loops, and counters, implementation

Insights — It should be read very carefully read and you must ask questions in between.

Question —

|s| is the length of string s. Form a new string b as follows.

String b is initially empty.

For each i where 1 ≤ i ≤ |s|:

• Append s[i-1] to the end of b.
• Reverse the string b.

Before creating b, reorder s to produce the b that is the lexicographically maximum possible.

Example

s = “011”.

Reorder s from “011” to “101”. String b is formed as follows

b after
           --------------	 
Operation  Append Reverse
---------  ------ -------
  1	     1      1
  2          10     01
  3          011    110

Return "101", the permutation of s that generates the maximum possible b.

Function Description

Complete the function getOptimalString in the editor below.