Quick Overview

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.

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/

Overview: 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

Hints

  1. A rearrangement is impossible if the maximum character frequency exceeds ceil(n/2).
  2. Build the answer greedily, one character at a time.
  3. At each step, pick the smallest letter different from the previous character.
  4. Before committing a choice, ensure the remaining multiset is still feasible: the maximum remaining count must be <= ceil(remaining_length/2).
  5. The alphabet size is small (26), enabling simple O(26) scans per position.

Loading coding console...

Show the approach

Approach

Goal: rearrange s so no two adjacent letters match, returning the lexicographically smallest such string, or "" if impossible.

Feasibility gate. A valid rearrangement exists iff the most frequent letter appears at most ceil(n/2) times. The code computes a 26-slot frequency array counts and immediately returns "" when max(counts) > (n + 1) // 2.

Greedy lex-smallest construction. The answer is built left-to-right. At each of the n positions it scans candidate letters a→z in order, skipping the letter just placed (prev) and any with counts[i] == 0. For each candidate it tentatively places the letter (counts[i] -= 1) and re-checks feasibility of the remaining multiset: the new maximum count max_after must satisfy max_after <= (remaining_after + 1) // 2. The first candidate that keeps the remainder feasible is committed (append the char, set prev, update remaining); otherwise the tentative decrement is reverted and the next letter is tried.

Why it's correct & smallest. Trying letters in increasing order and committing the first safe one is the classic exchange-argument greedy: picking any larger letter when a smaller one is safe could only produce a lexicographically larger result, and the per-step feasibility check (a tightened Hall-type condition on the dominant letter) guarantees the prefix can always be completed. If no candidate is safe at some position, it returns "" — though the global gate plus per-step check mean a well-formed feasible input never hits that.

Because the alphabet is a fixed 26 letters, both the candidate scan and the feasibility scan are constant work per position.

Time complexity:
O(n) — the outer loop runs n times; per position it scans up to 26 candidates and, for each, rescans 26 counts for feasibility, i.e. O(26²) constant work per position, giving O(n·26²) = O(n).
Space complexity:
O(1) auxiliary — a fixed 26-element `counts` array and scalar state; the O(n) `res`/output string is the required return value, not extra working space.