Solve LeetCode string and list problems
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 767. Reorganize String
LeetCode 23. Merge k Sorted Lists
LeetCode 138. Copy List with Random Pointer
https://leetcode.com/problems/reorganize-string/description/ https://leetcode.com/problems/merge-k-sorted-lists/description/ https://leetcode.com/problems/copy-list-with-random-pointer/description/
Quick Answer: This set of problems evaluates proficiency in string manipulation, priority-queue/heap usage and greedy strategies, and linked-list operations including pointer management and cloning, reflecting core data structure and algorithm competencies.
Given a string s of lowercase English letters, rearrange its characters so that no two adjacent characters are the same. Among all valid rearrangements, return the lexicographically smallest one. If no such rearrangement exists, return an empty string.
Constraints
- 1 <= len(s) <= 100000
- s consists only of lowercase English letters ('a' to 'z')
- If multiple valid rearrangements exist, return the lexicographically smallest
- If no valid rearrangement exists, return an empty string
Examples
Input: aaab
Expected Output:
Input: abb
Expected Output: bab
Input: a
Expected Output: a
Input: aab
Expected Output: aba
Input: aaabc
Expected Output: abaca
Input: aaaabc
Expected Output:
Hints
- A rearrangement is impossible if the maximum character frequency exceeds ceil(n/2).
- Build the answer greedily, one character at a time.
- At each step, pick the smallest letter different from the previous character.
- Before committing a choice, ensure the remaining multiset is still feasible: the maximum remaining count must be <= ceil(remaining_length/2).
- The alphabet size is small (26), enabling simple O(26) scans per position.