Determine if Two Strings Are Close
Medium · Arrays & Hashing · Hash Table · String · Sorting · Counting
Problem
Two operations may be applied to a word, as often as you like:
- Swap two positions: exchange any two characters, e.g. abcde → aecdb.
- Exchange two letters: pick two letters that both occur in the word and turn every occurrence of one into the other and back, e.g. aacabb → bbcbaa (every a becomes b and every b becomes a).
Two words are close if one can be turned into the other with these operations. Given word1 and word2, return true if they are close and false otherwise.
Examples
Input: word1 = "abc", word2 = "bca" Output: true
Swaps alone rearrange abc into bca.
Input: word1 = "a", word2 = "aa" Output: false
Neither operation changes the length.
Input: word1 = "cabbba", word2 = "abbccc" Output: true
cabbba has counts a:2, b:3, c:1 and abbccc has a:1, b:2, c:3. Exchanging letters can hand the counts 1, 2, 3 to any letters, and swaps fix the order.
Constraints
- 1 <= word1.length, word2.length <= 10^5
- word1 and word2 hold lowercase English letters
Approaches
- Sort the letters and the run lengths — time O(n log n), space O(n)
Follow-up
If only the letter exchange is allowed (positions fixed), the question becomes whether one consistent relabeling maps one word onto the other. And for a whole list of words, how many groups of mutually close words are there?
Related problems
Start free on Cariara · Coding problems · System design studio
