Solve LeetCode array & stream problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### 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/
Quick Answer: This set of problems evaluates proficiency in array and string manipulation, stream processing, order-preserving deduplication, stability-aware sorting, and analysis of time/space complexity within the Coding & Algorithms domain.
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
Solution
from collections import defaultdict
def group_shifted_strings(strings: list[str]) -> list[list[str]]:
def signature(s: str) -> tuple:
if len(s) <= 1:
return ()
diffs = []
prev = ord(s[0]) - 97
for ch in s[1:]:
curr = ord(ch) - 97
diffs.append((curr - prev) % 26)
prev = curr
return tuple(diffs)
buckets: dict[tuple, list[str]] = defaultdict(list)
for s in strings:
buckets[signature(s)].append(s)
groups: list[list[str]] = []
for group in buckets.values():
group.sort()
groups.append(group)
groups.sort(key=lambda g: g[0])
return groups
Explanation
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).
Hints
- Two strings belong to the same group if their sequences of consecutive letter differences modulo 26 are identical.
- All single-character strings share the same signature (empty difference sequence).
- Use a hash map from signature to list of strings; then sort each bucket and sort the buckets by their first element.