Solve frequency sort and all-pairs sum

Task 1 — Frequency-based string reorder: Given a string s containing ASCII characters, return a new string whose characters are ordered by decreasing frequency; when two characters share the same frequency, order them by ascending character code. Describe your chosen data structures and provide time and space complexity. Task 2 — All unique two-sum pairs in sorted array: Given a nondecreasing sorted integer array nums and an integer target, return all unique index pairs (i, j) with i < j such that nums[i] + nums[j] == target. Avoid duplicate pairs when values repeat. Achieve O(n) time and O(1) extra space (excluding the output) using a two-pointer method. Explain your deduplication strategy and analyze complexity.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Frequency-Based String Reorder

Given a string s containing ASCII characters, return a new string whose characters are ordered by decreasing frequency. When two characters share the same frequency, order them by ascending character code (i.e., ASCII value). Each character must appear in the output exactly as many times as it appears in the input.

This is the classic "sort characters by frequency" problem (LeetCode 451) with a deterministic tie-break: equal-frequency characters are emitted in ascending ASCII order.

Example 1

Input:  s = "tree"
Output: "eert"

Explanation: 'e' appears twice, 'r' and 't' once each. 'e' (freq 2) comes first; 'r' and 't' tie at freq 1, so they are ordered by ascending char code: 'r' (114) then 't' (116).

Example 2

Input:  s = "Aabb"
Output: "bbAa"

Explanation: 'b' has freq 2 → first. 'A' (65) and 'a' (97) tie at freq 1; ascending char code puts 'A' before 'a'.

Describe your chosen data structures and provide the time and space complexity.

Constraints

• 0 <= len(s) <= 10^5
• s consists of printable ASCII characters
• Equal-frequency characters MUST be emitted in ascending ASCII order
• Each character appears in the output exactly as many times as in the input

Hints

1. Count each character's frequency with a hash map (or a fixed-size array of length 256 indexed by char code).
2. Sort the distinct characters by the key (-frequency, char_code): negative frequency gives descending frequency, char_code gives the ascending-ASCII tie-break.
3. Reconstruct the answer by repeating each character by its count in sorted order.

All Unique Two-Sum Pairs in a Sorted Array

Given a nondecreasing sorted integer array nums and an integer target, return all unique pairs of values [nums[i], nums[j]] with i < j such that nums[i] + nums[j] == target. Avoid duplicate pairs when values repeat (e.g., if nums contains several equal values, each distinct value-pair should appear at most once).

Return the pairs ordered by their left value ascending (which the two-pointer scan produces naturally). Achieve O(n) time and O(1) extra space (excluding the output) using a two-pointer method.

This generalizes the classic "Two Sum II — sorted input" (LeetCode 167): instead of stopping at the first matching pair, collect every distinct value-pair.

Example 1

Input:  nums = [1, 2, 3, 4, 4, 9, 56, 90], target = 8
Output: [[4, 4]]

Explanation: 4 + 4 = 8 is the only pair. Even though 4 appears twice, the value-pair [4,4] is reported once.

Example 2

Input:  nums = [1, 1, 2, 2, 3, 3], target = 4
Output: [[1, 3], [2, 2]]

Explanation: 1+3 and 2+2 both equal 4; duplicates of 1 and 3 are skipped so [1,3] appears once.

Explain your deduplication strategy and analyze complexity.

Constraints

• 0 <= len(nums) <= 10^5
• nums is sorted in nondecreasing order
• -10^9 <= nums[i], target <= 10^9
• Report each distinct value-pair at most once (dedup on repeated values)
• Required: O(n) time, O(1) extra space (excluding output), two-pointer method

Hints

1. Place one pointer at the start and one at the end. If the sum is too small, advance the left pointer; if too large, retreat the right pointer.
2. When you find a match, record the value-pair, then skip over ALL further equal values on both sides before continuing — this is the deduplication step.
3. Because the array is sorted, equal values are contiguous, so skipping them with while-loops keeps the scan O(n) overall and prevents duplicate pairs.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Task 1 — Frequency-based string reorder: Given a string s containing ASCII characters, return a new string whose characters are ordered by decreasing frequency; when two characters share the same frequency, order them by ascending character code. Describe your chosen data structures and provide time and space complexity. Task 2 — All unique two-sum pairs in sorted array: Given a nondecreasing sorted integer array nums and an integer target, return all unique index pairs (i, j) with i < j such that nums[i] + nums[j] == target. Avoid duplicate pairs when values repeat. Achieve O(n) time and O(1) extra space (excluding the output) using a two-pointer method. Explain your deduplication strategy...

Recommended Approach

Use the string constraints to choose between two pointers, a stack, frequency counts, prefix/suffix state, or dynamic programming. Maintain the invariant that processed characters have already been normalized, counted, or matched according to the operation.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Most direct string scans are O(n) time. Space ranges from O(1) for two pointers to O(n) for stacks, maps, or DP tables.

Edge Cases and Tests

Empty string, length 1, repeated characters, invalid characters, case sensitivity, Unicode vs ASCII, and very long input.