How should I practice Reorganize a String?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon onsite interview problems in FastPrep.

Is Reorganize a String associated with Amazon?

FastPrep tags this as a Amazon onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · String

Reorganize a String

Learn this problem

● Medium

AmazonINTERNONSITE INTERVIEW

See Amazon hiring insights

Problem statement

Rearrange a lowercase string so that no two adjacent characters are equal. If no such arrangement exists, return the empty string.

To make the judged result deterministic, construct the answer with this rule: at each position, select the eligible character with the greatest remaining frequency. The previously placed character is not eligible. If several eligible characters have the same frequency, select the lexicographically smallest one.

Function

reorganizeString(s: String) → String

Examples

Example 1

s = "aab"return = "aba"

The highest-frequency eligible character is chosen first, producing a valid arrangement.

Example 2

s = "aaab"return = ""

Three copies of one character cannot be separated by the single remaining character.

Example 3

s = "aabbcc"return = "abcabc"

Frequency ties are resolved in lexicographic order while the previous character remains temporarily ineligible.

Constraints

1 <= s.length <= 10^5
s contains only lowercase English letters.