Katkat
Back

Can board states be transformed?

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to determine if one board state can be transformed into another using reversible movement rules, requiring the identification of invariants to avoid exhaustive searching.

Problem Statement

You are given a board represented as a string of length N containing exactly two types of pieces: 'A' and 'B', and an empty space denoted by '.'.

You can perform the following moves:

  1. An 'A' can move into an adjacent empty space '.' (e.g., "A." becomes ".A" or ".A" becomes "A.").
  2. A 'B' can jump over an adjacent 'A' if the space behind the 'A' is empty (e.g., "BA." becomes ".AB").

Given an initial state start and a target state end, determine if it is possible to transform start into end through any number of moves. Both strings will have the same length N and the same counts of 'A', 'B', and '.' pieces.

Function Signature

def can_transform(start: str, end: str) -> bool:

Examples

Example 1: Input: start = "A.B", end = "B.A" Output: False Explanation: Even though they are the same pieces, the relative order of A and B is fixed based on the rules.

Example 2: Input: start = "BA..", end = "..AB" Output: True

Constraints

  • 1 <= N <= 10^5
  • The string contains only 'A', 'B', and '.'
  • Time complexity should be O(N).

Hints

Hint 1

Ignore the '.' characters first; does the relative order of 'A' and 'B' pieces remain constant regardless of the moves?

Hint 2

If the relative order of pieces is invariant, what additional constraints do the '.' positions impose on the movement of 'A' vs 'B'?

Hint 3

Consider the relative indices of 'A's and 'B's in the start and end strings while ignoring the empty spaces.

Follow-up questions

  • How does the complexity change if you are allowed to move 'B' pieces into any empty space, not just by jumping over an 'A'?
  • If the board were a 2D grid instead of a 1D string, what new topological invariants would you need to consider?
  • Can you provide a constructive proof for why the relative order of pieces cannot change given these specific rules?