All problems

Determine if Two Strings Are Close

Medium · hash map

You are given two words, word1 and word2, made of lowercase letters. You may change word1 as many times as you like using these two moves:

  1. Swap two positions. Pick any two positions in the word and swap the letters standing there.
  2. Swap two letters everywhere. Pick two different letters that both appear in the word. Every copy of the first becomes the second, and every copy of the second becomes the first, all at once. For example, with a and b, the word "aabcb" becomes "bbaca".

Return true if some sequence of moves turns word1 into word2, and false otherwise. Using no moves at all is allowed.

Examples

Example 1

Input: word1 = "abc", word2 = "bca"

Output: true

Swapping positions is enough: the same letters in a different order.

Example 2

Input: word1 = "aaab", word2 = "aabb"

Output: false

One word has a letter three times and another once; the other has two of each. No move changes that mix of counts.

Example 3

Input: word1 = "cabbba", word2 = "abbccc"

Output: true

Swap "a" and "b" everywhere to get "cbaaab", swap "a" and "c" everywhere to get "abcccb", then swap positions to reach "abbccc".

Constraints