Determine if Two Strings Are Close
The key idea
Operation 1 (swap two characters) lets you reorder freely, so position never matters. Operation 2 (transform every occurrence of one existing character into another existing one) lets you reassign which letter owns which count, but it can never create a new letter or change how many distinct counts exist. So two strings are close iff they share the exact same set of characters AND the same multiset of frequencies.
Problem
Two strings are considered close if you can attain one from the other using the following operations:
- Operation 1: Swap any two existing characters. For example, abcde -> aecdb.
- Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character. For example, aacabb -> bbcbaa (all a's turn into b's, and all b's turn into a's).
You can use the operations on either string as many times as necessary.
Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.
Constraints
- 1 <= word1.length, word2.length <= 10^5
- word1 and word2 contain only lowercase English letters.
Examples
Input: word1 = "abc", word2 = "bca"
Output: true
Input: word1 = "a", word2 = "aa"
Output: false
Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Complexity
Time: O(n + k log k) Space: O(k)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM