Amazon Coding Question 2020 Help

Please give me approach as well as short and sweet code; remember short and sweet

Amazon is looking to develop a new labeling system in the fulfillment centers. New labels will be devised from the original string labels. Given the original string label, construct a new string by rearranging the original string and deleting characters as needed. Return the alphabetically-largest string that can be constructed respecting the limit as to how many consecutive characters can be the same (represented by k).
“Alphabetically-largest” is defined in reverse alphabetical order (e.g., b is “larger” than a, c is “larger” than b, etc.) from left to right (e.g., “ba” is larger than “ab”).
Write an algorithm to return the alphabetically-largest string that can be constructed respecting the above limits.

Input
The input to the function/method consists of two arguments:
originalLabel, a string representing the original string label;
charlimit, an integer representing the maximum number of identical consecutive characters the new string can have (k).

Output
Return a string representing the alphabetically largest string that can be constructed that has no more than k identical consecutive characters.

Constraints
1 <= len <= 10^5; where len represents the length of originalLabel
1 <= charlimit <= 10^3

Note
The string originalLabel contains only lowercase English letters.

Example
Input:
originalLabel = baccc
charLimit = 2

Output:
ccbca

Explanation:
The largest string, alphabetically, is ‘cccba’ but it is not allowed because it uses the character’s more than 2 times consecutively. Therefore, the answer is ‘ccbca’.

Thanks in advance!!!

map<char,int>m;
priority_queuepq;
int k=2;
string original;cin>>original;
int n=original.size();
fr(0,n)m[original[i]]++;
for(auto x:m)pq.push(x.F);
string ans;
ans+=pq.top();
m[pq.top()]–;
if(m[pq.top()]==0){
pq.pop();
}
int same=1;
int c=1;
while(!pq.empty()){

    if (same>=k){
        char tp=pq.top();
        if(tp!=ans[c-1]){
            ans+=pq.top();
            m[pq.top()]--;
            if(m[pq.top()]==0){
                m.erase(pq.top());
                pq.pop();
            }
        }
        else{
            pq.pop();
            ans+=pq.top();
            m[pq.top()]--;
            if(m[pq.top()]==0){
                m.erase(pq.top());
                pq.pop();
            }
            pq.push(tp);
            same=1;
        }
    }
    else{
        ans+=pq.top();
        m[pq.top()]--;
        if(m[pq.top()]==0){
            m.erase(pq.top());
            pq.pop();
        }
    }
    if (ans[c-1]==ans[c])same++;
    c++;
}
trace(ans);
TC=O(nlog(n))
//IF POSSIBLE THEN IT WILL GIVE THE ANSWER ELSE ANSWER DOES NOT EXIST FOR CASES SUCH AS (aaaaa and k=2) AND WE CAN CHECK FOR IT SEPERATELY

Hey, This Problem is greedy Problem ,as far as i can observe it.
In this problem what we can do is that make freq array of characters and iterate in reverse manner ( as we can rearrange the characters this doesn’t affect our solution )
so from now onwards i am explaining the algo with an example it makes easy to you to understand.
Let say given string is aabbbzzzz limit is 3
freq array looks like (a,2) (b,3) (z,4). initial ans=""(empty)
As i mentioned iterate in reverse fashion means we start from z
take 3 chars from z (now ans = “zzz”) (as limit is 3 ) (if we took another z anslimit>reqlimit so we can’t take it so you have to add some other char in between )
now you want this to be largest what you will pick obviously b ( to make it largest )
so we took 1 b ( now ans = “zzzb” )
now we took the remaining z in same fashion so (ans = “zzzbz”)
and our freq array looks like this (a,2) (b,2) (z,0).
Problem Reduced to find out the largest string with charlimit 3 ( whatever you ans for reduced problem is let say X. your ans will be (what you find here)+(X))
Pseudo code
///Sweet PsuedoCode Begins
#define chlimit ch

1. Make a freq Array of characters
2. iterate in reverse fashion
3. if we can not take ch char from current
       3.1 take max we can take from current position
      continue your iteration
   Otherwise
   take ch characters from current pointer
   look at nearest char in left and put it in your string (take only 1 char from it)
  if there is no characters in left{
     output the string;
     return
  }
 Otherwise
  continue
1 Like

can you tell me why answer do not exist for aaaa and k=2. it is given in the question that we can delete the characters if we required :stuck_out_tongue:

was it oncampus hiring or offcampus??

I misreaded the question.
Thanks for reminding


let longestString = (input, charLimit) => {
// sort the string to be the longest
let longestString = input.split(’’).sort().reverse()

// iterate through longest string change position of char
// if the charLimit is reached
let limitCount = 0
for(let i=0; i<longestString.length-1; ++i) {
// same char but under same charLimit
if(longestString[i+1] === longestString[i] && limitCount < charLimit) {
++limitCount
}

// same char and on same charLimit
// change position with next different char and reset limit
if(longestString[i+1] === longestString[i] && limitCount === charLimit) {
  let k=i+1
  for(k; k<longestString.length; ++k) {
    if(longestString[i+1] !== longestString[k]) {
      break
    }
  }
  // k is position of next different char change it with pos i+1
  // three way change
  let tmp = longestString[i+1]
  longestString[i+1] = longestString[k] 
  longestString[k] = tmp

  // reset limitCount
  limitCount = 0
}

// different char 
// reset limitCount
if(longestString[i+1] !== longestString[i]) {
  limitCount = 0
}

}

return longestString.join(’’)
}


console.log(longestString(‘baccc’, 2))
console.log(longestString(‘cccba’, 2))
console.log(longestString(‘cccba’, 3))
console.log(longestString(‘aaara’, 2))
console.log(longestString(‘aaaaa’, 2))


It’s js don’t know if it is 100 % correct test cases seem to work

@jeeadvanced you nailed it !!! Thanks bro

off

for which year is it aplly??

Can you tell me what other questions you were asked in the test ?