Solve LeetCode string and list problems

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/

Lexicographically Smallest Reorganized String

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

Example 1

Input: s = "aab"
Output: "aba"

Explanation: A valid rearrangement with no equal adjacent characters is "aba". It is the lexicographically smallest among valid options.

Example 2

Input: s = "aaabbc"
Output: "ababac"

Explanation: One valid smallest arrangement is "ababac". No two adjacent characters are the same, and it is lexicographically smallest among all valid rearrangements.

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.

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.