# 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

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.

getOptimalString has the following parameter:

s: a string

Returns

string: the permutation of s that generates the maximal b

Constraints

• 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

`STDIN        FUNCTION-----        --------1100    →    s = "1100"`

`0101`

## Explanation

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

`STDIN        FUNCTION-----        --------111     →    s = "111"`

Sample Output

`111`

Explanation

The result string is already lexicographically maximum.

# Solution

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.        ans.append(s[n//2])    i = (n + 1)//2 # from mid to end    j = (n - 2)//2 # from mid to front    while j>=0 and i < n:        ans.append(s[i])        ans.append(s[j])        i += 1;        j -= 1    return ''.join(ans)`

Code (C++):

`string getOptimalString(string s) {    string ans;    int n=s.length();    sort(s.begin(),s.end());    reverse(s.begin(),s.end());    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++){        ans.push_back(s[i]);        ans.push_back(s[j]);    }    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)

--

--

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