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

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)