You are given two 0-indexed strings word1 and word2.
A move consists of choosing two indices i and j such that 0 <= i < word1.length and 0 <= j < word2.length and swapping word1[i] with word2[j].
Return true if it is possible to get the number of distinct characters in word1 and word2 to be equal with exactly one move. Return false otherwise.
Example 1:
Input: word1 = "ac", word2 = "b" Output: false Explanation: Any pair of swaps would yield two distinct characters in the first string, and one in the second string.
Example 2:
Input: word1 = "abcc", word2 = "aab" Output: true Explanation: We swap index 2 of the first string with index 0 of the second string. The resulting strings are word1 = "abac" and word2 = "cab", which both have 3 distinct characters.
Example 3:
Input: word1 = "abcde", word2 = "fghij" Output: true Explanation: Both resulting strings will have 5 distinct characters, regardless of which indices we swap.
Constraints:
1 <= word1.length, word2.length <= 105word1andword2consist of only lowercase English letters.
Companies: Google
Related Topics:
Hash Table, String, Counting
Similar Questions:
- Bulls and Cows (Medium)
- Buddy Strings (Easy)
- Minimum Swaps to Make Strings Equal (Medium)
- Check if One String Swap Can Make Strings Equal (Easy)
- Check if All Characters Have Equal Number of Occurrences (Easy)
// OJ: https://leetcode.com/problems/make-number-of-distinct-characters-equal
// Author: github.com/lzl124631x
// Time: O(M + N)
// Space: O(1)
class Solution {
public:
bool isItPossible(string s, string t) {
int cs[26] = {}, us = 0, ct[26] = {}, ut = 0;
for (char c : s) us += cs[c - 'a']++ == 0;
for (char c : t) ut += ct[c - 'a']++ == 0;
for (int i = 0; i < 26; ++i) {
if (cs[i] == 0) continue;
us -= cs[i]-- == 1;
for (int j = 0; j < 26; ++j) {
if (ct[j] == 0) continue;
ut -= ct[j]-- == 1;
us += cs[j]++ == 0;
ut += ct[i]++ == 0;
if (us == ut) return true;
ut -= ct[i]-- == 1;
us -= cs[j]-- == 1;
ut += ct[j]++ == 0;
}
us += cs[i]++ == 0;
}
return false;
}
};