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
Solution
def reorganize_string_lex_smallest(s: str) -> str:
n = len(s)
if n <= 1:
return s
# Frequency of each lowercase letter
counts = [0] * 26
for ch in s:
counts[ord(ch) - 97] += 1
# Global feasibility check
if max(counts) > (n + 1) // 2:
return ""
res = []
prev = -1 # index of previously placed character
remaining = n
for _ in range(n):
chosen = -1
for i in range(26):
if i == prev or counts[i] == 0:
continue
# Tentatively place character i
counts[i] -= 1
remaining_after = remaining - 1
# Check feasibility of the remainder
max_after = 0
for c in counts:
if c > max_after:
max_after = c
if max_after <= (remaining_after + 1) // 2:
# Commit choice
chosen = i
res.append(chr(97 + i))
prev = i
remaining = remaining_after
break
# Revert tentative choice and try next
counts[i] += 1
if chosen == -1:
# No valid next character
return ""
return "".join(res)
Explanation
We first check global feasibility: a solution exists iff the highest frequency does not exceed ceil(n/2). To obtain the lexicographically smallest valid rearrangement, we construct the answer left-to-right. At each position, we try characters in increasing order, skipping the previous character to avoid adjacent duplicates. For each candidate, we temporarily decrement its count and verify that the remaining multiset is still feasible (the maximum remaining count is at most ceil(remaining_length/2)). If feasible, we commit that character; otherwise, we revert and try the next. Because the alphabet size is a small constant (26), checking feasibility by scanning counts is efficient, and this greedy process yields the lexicographically smallest valid string.
Time complexity: O(n). Space complexity: O(1).
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.