# 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.

*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"

## Sample Output

`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

- appending characters to begin
- 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)