Solve LeetCode array & stream problems

Question

LeetCode 346. Moving Average from Data Stream

LeetCode 249. Group Shifted Strings

LeetCode 163. Missing Ranges

Remove duplicates from a character sequence while preserving original order

"Hidden Gem" array/string manipulation problem (exact LC title unknown)

Return elements in sorted order while maintaining relative stability and optimizing complexity

https://leetcode.com/problems/moving-average-from-data-stream/description/ https://leetcode.com/problems/group-shifted-strings/description/ https://leetcode.com/problems/missing-ranges/description/

Group Shifted Strings with Deterministic Ordering

Given a list of non-empty lowercase strings, group them by shift-equivalence. Two strings s and t are shift-equivalent if there exists an integer k in [0, 25] such that shifting every character in s forward by k positions in the alphabet (with wrap-around, so 'z' + 1 -> 'a') yields t. Return all groups of shift-equivalent strings. For deterministic output, within each group return strings sorted in ascending lexicographic order, and sort the list of groups by each group's first string. Preserve duplicates as separate entries.

Constraints

• 1 <= len(strings) <= 10^4
• 1 <= len(s) <= 20 for each s in strings
• strings[i] consists only of lowercase English letters 'a' to 'z'
• Output ordering: sort each group lexicographically; then sort groups by each group's first string
• Duplicates in input are preserved in their respective groups

Examples

Example 1

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]
Output: [["a","z"],["abc","bcd","xyz"],["acef"],["az","ba"]]

Explanation: Groups by signature: (1,1): [abc,bcd,xyz], (25): [az,ba], ():[a,z], (2,2,1):[acef]. Sort within groups and then by first element gives [["a","z"],["abc","bcd","xyz"],["acef"],["az","ba"]].

Example 2

Input: strings = ["aa","bb","z"]
Output: [["aa","bb"],["z"]]

Explanation: aa and bb have consecutive differences (0); z is single-character with signature (). Sort within groups and then by first element.

Hints

1. Two strings belong to the same group if their sequences of consecutive letter differences modulo 26 are identical.
2. All single-character strings share the same signature (empty difference sequence).
3. Use a hash map from signature to list of strings; then sort each bucket and sort the buckets by their first element.

Approach

Map each string to a signature representing its consecutive character differences modulo 26. Strings with the same signature are shift-equivalent. Collect strings into a hash map keyed by signature, then sort each group lexicographically. Finally, sort the list of groups by each group's first element to achieve deterministic ordering.

• Time complexity: O(n * k + n log n), where n is the number of strings and k is the average string length
• Space complexity: O(n)