HackerRank Coding Interview — String Conversion — Lexicographically Maximum Possible

Amber Ivanna Trujillo
2 min readMar 5


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.


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.

getOptimalString has the following parameter:

s: a string


string: the permutation of s that generates the maximal b


  • 1 ≤ |s| ≤ 10^5
  • The string s consists only of characters ‘0’ and ‘1’.

Input Format For Custom Testing

The first line contains a string, s.

Sample Case 0

Sample Input For Custom Testing

----- --------
1100 → s = "1100"

Sample Output



Using the permutation “0101”:

b after
Operation Append Reverse
--------- ------ -------
1 0 0
2 01 10
3 100 001
4 0011 1100

Sample Input For Custom Testing

----- --------
111 → s = "111"

Sample Output



The result string is already lexicographically maximum.


Concepts Covered: strings, loops, and counters, implementation

Optimal Solution

Since any permutation of string b can be formed.

We can fix the lexicographically-maximum-string b by sorting the string s.

We then can construct the required string s from string b.

The operation of converting string is like

  1. appending characters to begin
  2. and end one by one.

So we will keep 2 pointers at mid of b and move one pointer in a backward direction and the other in a forward direction to construct the final string s.

Code (Python):

def getOptimalString(s):
ans = []
n = len(s)
s = sorted(list(s), reverse = True) # descending sort
if n & 1: # if its odd, the middle element.
i = (n + 1)//2 # from mid to end
j = (n - 2)//2 # from mid to front
while j>=0 and i < n:
i += 1;
j -= 1
return ''.join(ans)

Code (C++):

string getOptimalString(string s) {
string ans;
int n=s.length();
if(n%2) ans.push_back(s[n/2]);
for(int i=(n+1)/2,j=(n-2)/2;j>=0 && i<n;j--,i++){
return ans;

Complexity Analysis

Time Complexity — The time complexity is O(n) where n is the length of the given string. Sorting complexity — nlog(n) , therfore the complexity is n(log(n))

Space Complexity — O(n)



Amber Ivanna Trujillo

I write about Technical stuff, interview questions, and finance Deep Learning, LLM, Startup, Influencer, Executive, Data Science Manager