Quick Overview

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.

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/

Overview: 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

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.

Loading coding console...

Show the approach

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)