0
$\begingroup$

This is a simple question I ran into in a remote interview:

Given a collection of letters, permute them (or one of its subset) into a string such that:

  • each letter can only be repeated for <= 11 times sequentially in the permutation

  • the string is lexicographically the largest

For one case, the collection of letters is:

zzzzzzzzzzzzzzzzzzzzzzzzzzzzyzzzzzzzyzzzyzzzzzzyzyzxyzzzzzzyzzxzyzyzyzzzyzyzzzzzzzyzzzzzzzzzzzzzzzzyzzzzzzzzzzzzzzzyyzzzzzzzzzzzzzzzzzzzzzzzyzzzyzzzzzzzyzzzzzzzzzzzyyzzzzzzzzzzyzzzzyzzzyzzzzzzzzzzzzyzzzzzzzzzzzzzyzzzzzzzzyzzzzzzzzzyzzzzzzyyzzyzzzzzzzzzzzzzzyzzzzzzzzzzzzzzzzzzzzzzzzzzyzzyyyyyzzzzzzzzzyzyzzzzzzzzzzzzzzxzzzzzzzyzzzzzzzzzyyzzzzyzzzzzzzzzzzzzzyzzzzzyzzzzzzzyzzzzzzzzzzzzzzyyzyzzzzyzzzyzzzzzzyzzzzzzzzyzzzzzzzyzzzzzzzzzzzzxxzzzzzzzzzzzzzzzzzzzzzxyzyzzzzzzzzzzzzzzzzzzyzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzyzzzzzzzzyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzxxzyzyzzyzzzzzzyzzzzxzzzzzzzzzzyzzzzyzzzzzzyzyzzzzzyzzyzyzzzzzzzzzzzzzzzzzzzzzzzzzzzzyzzzzzzzzyzzyyzyyzzzzzzyzyzzzzzzzzzyzzxzzzzyzzzyzzzyyzzzzzxzzzyyzzyzzzxyzzzzzzzzzzzzzyzyzzzzzzzzzzzzzzzyzzzyzzzzzzzzzyzzzzzzzzzzzxzzzzzzzzzzyzzyzzzzzzzzzzzzzzyyzyzzzyzzzzzzyzzzzzxzzzzzzzzzzzzzzzzzzzzzzzzzzzyyzyzzzzzzzzzzzzzzzzzyzzzzzzzzzzzzzzzzzzzzzyzzzzzzzzzyzzzzzzzzyzzzzzzzzzzzzzzzyzzzzzzxzyzxyzzzzzzzzzzzzzzzzzyzzzxzzzzzzzzzzzyzzzzzz

once converted to a multi-set, it contains:

  • 17 'x'
  • 114 'y'
  • 869 'z'

My answer for this case is:

zzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyyyyyyyyyyyxyyyyyyyyyyyxyyyyyyyyyyyxyyxxxyxxxxxxxxxxx

Then the interviewer AI kept telling me that my answer is sub-optimal.

I've tried to find a better answer but it appears that none is available. Can you give a better answer for this case?

(Sorry due to the NDA I'm not allowed to write my code here, but it is a simple algorithm of greedy finite-state automaton with no backtracking + preemptive pruning)

$\endgroup$
1
  • 1
    $\begingroup$ (I can't, and not for lack of checking.) $\endgroup$
    – greybeard
    Jun 19 '21 at 20:56
3
$\begingroup$

"permute them (or one of its subset) into a string"

This subset is better:

zzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyzzzzzzzzzzzyyyyyyyyyyyxyyyyyyyyyyyxyyyyyyyyyyyxyyy

$\endgroup$
6
  • $\begingroup$ You are right, but sorry I made a mistake about the condition, "lexicographically the largest" doesn't mean "rank the last", it means if converted to a number with base26 numeral system, it will be the largest (which means longer string are always preferred) $\endgroup$
    – tribbloid
    Jun 20 '21 at 17:03
  • $\begingroup$ @tribbloid If the longer string is always preferred, then your answer is optimal my friend unless I am missing something. Also, then the statement "permute them (or one of its subset) into a string" is not significant in the question. $\endgroup$ Jun 20 '21 at 17:21
  • $\begingroup$ Could you add another 11 x? $\endgroup$
    – gnasher729
    Jun 20 '21 at 19:29
  • $\begingroup$ @gnasher729 yes we can. $\endgroup$ Jun 20 '21 at 19:37
  • 1
    $\begingroup$ @InuyashaYagami it is not significant for the case, but sometimes you got >23 z and 1 y and nothing else $\endgroup$
    – tribbloid
    Jun 23 '21 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.