Solve Three Algorithmic Problems

Three coding questions were mentioned:

1. Second-largest distinct permutation Given an array of integers that may contain duplicates, consider all distinct permutations of the array ordered from largest to smallest in lexicographic order. Return the second-largest distinct permutation.

   Examples:

   • [1, 2, 3, 4, 5] -> [5, 4, 3, 1, 2]
   • [1, 1, 5] -> [1, 5, 1]

   You may assume there are at least two distinct permutations.

2. Merge m sorted arrays and return first k values You are given m integer arrays, each already sorted in non-decreasing order. Return the first k values in globally sorted order across all arrays. Preserve duplicates.

3. Choose a subset of words with no repeated characters Given a list of words, choose a subset whose concatenation contains no repeated characters. Maximize the total number of unique characters in the concatenated result. A word that contains duplicate characters internally cannot be part of any valid solution unless those duplicates are allowed by the rules; assume the final concatenation must contain each character at most once. Discuss an algorithm that still works when the input contains thousands of words.

Part 1: Second-Largest Distinct Permutation

Given an integer array nums that may contain duplicates, consider all distinct permutations of nums ordered from largest to smallest in lexicographic order. Return the second permutation in that ordering. You may assume there are at least two distinct permutations.

Constraints

• 2 <= len(nums) <= 200000
• -10^9 <= nums[i] <= 10^9
• There are at least two distinct permutations of nums, so not all elements are identical.

Examples

Example 1

Input: [1, 2, 3, 4, 5]
Output: [5, 4, 3, 1, 2]

Explanation: The largest permutation is [5, 4, 3, 2, 1], and the next distinct one below it is [5, 4, 3, 1, 2].

Example 2

Input: [1, 1, 5]
Output: [1, 5, 1]

Explanation: Distinct permutations in descending lexicographic order are [5, 1, 1], [1, 5, 1], [1, 1, 5].

Hints

1. What is the largest lexicographic permutation you can build from the multiset of values?
2. After building the largest one, apply the previous-permutation idea exactly once.

Part 2: Merge M Sorted Arrays and Return First K Values

You are given m integer arrays, each already sorted in non-decreasing order. Return the first k values in globally sorted order across all arrays. Preserve duplicates. If the total number of available values is less than k, return all of them.

Constraints

• 0 <= len(arrays) <= 100000
• Each inner array is sorted in non-decreasing order
• 0 <= total number of elements across all arrays <= 200000
• 0 <= k <= 200000

Examples

Example 1

Input: ([[1, 4, 7], [2, 5], [3, 6, 8]], 5)
Output: [1, 2, 3, 4, 5]

Explanation: The global sorted order begins 1, 2, 3, 4, 5, 6, 7, 8.

Example 2

Input: ([[1, 1, 2], [1, 3], []], 4)
Output: [1, 1, 1, 2]

Explanation: Duplicates must be preserved, and empty arrays should be ignored.

Hints

1. You do not need to merge every value if you only need the first k answers.
2. Keep one candidate from each non-empty array in a min-heap.

Part 3: Maximum Unique-Character Concatenation

Given a list of lowercase words, choose a subset whose concatenation contains no repeated characters. Return the maximum possible number of characters in such a concatenation. Any word that repeats a character inside itself cannot be part of a valid answer. Your algorithm should remain practical even when the input contains thousands of words.

Constraints

• 0 <= len(words) <= 5000
• 0 <= len(word) <= 26
• Each word contains only lowercase English letters a-z

Examples

Example 1

Input: ["un", "iq", "ue"]
Output: 4

Explanation: One optimal choice is ["un", "iq"], which gives 4 unique characters.

Example 2

Input: ["ab", "cd", "aef", "gh"]
Output: 7

Explanation: Choosing ["cd", "aef", "gh"] yields 7 unique characters.

Hints

1. Convert each valid word into a 26-bit mask. If a word contains the same letter twice, discard it immediately.
2. Because there are only 26 possible letters, memoizing by a letter-mask state can be far more scalable than naive subset enumeration over all words.