Show problems as
Classic problem #2840MediumHash TableStringSorting

Check if Strings Can be Made Equal With Operations II

Real-world version: Matching Tile Runs With Parity Swaps
Tracked in this browser only
Read Check if Strings Can be Made Equal With Operations II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two display rails, left and right, each carry the same number of tiles. A tile is written as a lowercase letter, its colour. Seats on a rail are numbered from 0.

A fitter may repeat this move as often as they like, on either rail: pick two seats on the same rail whose numbers are both even or both odd, and swap the tiles sitting in them. Seats do not have to be next to each other.

Return true if the two rails can be made to show the same colours in the same seats, and false otherwise.

Examples

Example 1

Input
left = "abcd", right = "cbad"
Output
true

Swapping the tiles in seats 0 and 2 of `left` turns it into "cbad", which is what `right` already shows.

Example 2

Input
left = "axaxbx", right = "axbxbx"
Output
false

The even seats of `left` carry a, a and b, while the even seats of `right` carry a, b and b, and no permitted move changes either of those groups. So the rails cannot be made to agree.

Example 3

Input
left = "ab", right = "ba"
Output
false

Seats 0 and 1 have different parity, so no permitted move touches this pair of tiles at all and the rails stay different.

Constraints

  • n == left.length == right.length
  • 1 <= n <= 10^5
  • left and right hold only lowercase English letters.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def can_match_runs(left: str, right: str) -> bool:
Java
public boolean canMatchRuns(String left, String right)

More on the same topics