2531. Make Number of Distinct Characters Equal
Description
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 <= 105
word1
andword2
consist of only lowercase English letters.
Solutions
Solution 1: Counting + Enumeration
We first use two arrays $\textit{cnt1}$ and $\textit{cnt2}$ of length $26$ to record the frequency of each character in the strings $\textit{word1}$ and $\textit{word2}$, respectively.
Then, we count the number of distinct characters in $\textit{word1}$ and $\textit{word2}$, denoted as $x$ and $y$ respectively.
Next, we enumerate each character $c1$ in $\textit{word1}$ and each character $c2$ in $\textit{word2}$. If $c1 = c2$, we only need to check if $x$ and $y$ are equal; otherwise, we need to check if $x - (\textit{cnt1}[c1] = 1) + (\textit{cnt1}[c2] = 0)$ and $y - (\textit{cnt2}[c2] = 1) + (\textit{cnt2}[c1] = 0)$ are equal. If they are equal, then we have found a solution and return $\text{true}$.
If we have enumerated all characters and have not found a suitable solution, we return $\text{false}$.
The time complexity is $O(m + n + |\Sigma|^2)$, where $m$ and $n$ are the lengths of the strings $\textit{word1}$ and $\textit{word2}$, and $\Sigma$ is the character set. In this problem, the character set consists of lowercase letters, so $|\Sigma| = 26$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|