Quick Overview

This pair of problems evaluates proficiency with string-processing algorithms and advanced data structures for matching, alongside state-space graph search techniques and state-encoding strategies.

Solve palindrome pairs and key path

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question LeetCode 336. Palindrome Pairs; LeetCode 864. Shortest Path to Get All Keys https://leetcode.com/problems/palindrome-pairs/description/ https://leetcode.com/problems/shortest-path-to-get-all-keys/description/

Overview: This pair of problems evaluates proficiency with string-processing algorithms and advanced data structures for matching, alongside state-space graph search techniques and state-encoding strategies.

You are given an m x n grid of characters representing a maze. The grid contains exactly one start cell '@', walls '#', empty cells '.', lowercase keys 'a' to 'f', and uppercase locks 'A' to 'F'. You can move up, down, left, or right by one cell per step. You can pass through a lock only if you have collected its corresponding key (e.g., key 'a' opens lock 'A'). Collecting a key adds it to your set permanently. Return the minimum number of steps required to collect all keys present in the grid. If it is impossible, return -1. If there are no keys, return 0.

Constraints

  • 1 <= m, n <= 30
  • Grid size m * n <= 900
  • Grid characters are '@', '#', '.', 'a'-'f', 'A'-'F' only
  • Exactly one start cell '@'
  • At most 6 distinct keys ('a'..'f')
  • Movement allowed in 4 directions (up, down, left, right) with cost 1 per step
  • You cannot move outside the grid or into walls '#'

Hints

  1. Use BFS where each state is (row, col, keyMask).
  2. Represent collected keys with a bitmask; bit i corresponds to key chr(ord('a')+i).
  3. Precompute the target key mask by scanning the grid.
  4. Maintain visited states by (row, col, keyMask) to avoid revisiting.
  5. When encountering a lock 'A'-'F', ensure the corresponding bit is set in keyMask before moving through.

Loading coding console...

Show the approach

Approach

Perform BFS over an augmented state space (row, col, keyMask). The keyMask records which keys have been collected using bits. Precompute the target mask by scanning the grid. From each state, explore four neighbors if within bounds and not a wall. You may pass a lock only if the corresponding key bit is set. When moving onto a key cell, set its bit in the mask; if this equals the target mask, return the steps taken so far plus one. Use a visited set keyed by (row, col, keyMask) to prevent revisiting states. BFS guarantees the first time all keys are collected is optimal.

Time complexity:
O(m * n * 2^k), where k <= 6 is the number of distinct keys
Space complexity:
O(m * n * 2^k) for the visited state set and BFS queue