Welcome to Subscribe On Youtube

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 and word2 consist of only lowercase English letters.

Solutions

  • class Solution {
        public boolean isItPossible(String word1, String word2) {
            int[] cnt1 = new int[26];
            int[] cnt2 = new int[26];
            for (int i = 0; i < word1.length(); ++i) {
                ++cnt1[word1.charAt(i) - 'a'];
            }
            for (int i = 0; i < word2.length(); ++i) {
                ++cnt2[word2.charAt(i) - 'a'];
            }
            for (int i = 0; i < 26; ++i) {
                for (int j = 0; j < 26; ++j) {
                    if (cnt1[i] > 0 && cnt2[j] > 0) {
                        --cnt1[i];
                        --cnt2[j];
                        ++cnt1[j];
                        ++cnt2[i];
                        int d = 0;
                        for (int k = 0; k < 26; ++k) {
                            if (cnt1[k] > 0) {
                                ++d;
                            }
                            if (cnt2[k] > 0) {
                                --d;
                            }
                        }
                        if (d == 0) {
                            return true;
                        }
                        ++cnt1[i];
                        ++cnt2[j];
                        --cnt1[j];
                        --cnt2[i];
                    }
                }
            }
            return false;
        }
    }
    
  • class Solution {
    public:
        bool isItPossible(string word1, string word2) {
            int cnt1[26]{};
            int cnt2[26]{};
            for (char& c : word1) {
                ++cnt1[c - 'a'];
            }
            for (char& c : word2) {
                ++cnt2[c - 'a'];
            }
            for (int i = 0; i < 26; ++i) {
                for (int j = 0; j < 26; ++j) {
                    if (cnt1[i] > 0 && cnt2[j] > 0) {
                        --cnt1[i];
                        --cnt2[j];
                        ++cnt1[j];
                        ++cnt2[i];
                        int d = 0;
                        for (int k = 0; k < 26; ++k) {
                            if (cnt1[k] > 0) {
                                ++d;
                            }
                            if (cnt2[k] > 0) {
                                --d;
                            }
                        }
                        if (d == 0) {
                            return true;
                        }
                        ++cnt1[i];
                        ++cnt2[j];
                        --cnt1[j];
                        --cnt2[i];
                    }
                }
            }
            return false;
        }
    };
    
  • class Solution:
        def isItPossible(self, word1: str, word2: str) -> bool:
            cnt1 = [0] * 26
            cnt2 = [0] * 26
            for c in word1:
                cnt1[ord(c) - ord('a')] += 1
            for c in word2:
                cnt2[ord(c) - ord('a')] += 1
            for i, a in enumerate(cnt1):
                for j, b in enumerate(cnt2):
                    if a and b:
                        cnt1[i], cnt2[j] = cnt1[i] - 1, cnt2[j] - 1
                        cnt1[j], cnt2[i] = cnt1[j] + 1, cnt2[i] + 1
                        if sum(v > 0 for v in cnt1) == sum(v > 0 for v in cnt2):
                            return True
                        cnt1[i], cnt2[j] = cnt1[i] + 1, cnt2[j] + 1
                        cnt1[j], cnt2[i] = cnt1[j] - 1, cnt2[i] - 1
            return False
    
    
  • func isItPossible(word1 string, word2 string) bool {
    	cnt1 := [26]int{}
    	cnt2 := [26]int{}
    	for _, c := range word1 {
    		cnt1[c-'a']++
    	}
    	for _, c := range word2 {
    		cnt2[c-'a']++
    	}
    	for i := range cnt1 {
    		for j := range cnt2 {
    			if cnt1[i] > 0 && cnt2[j] > 0 {
    				cnt1[i], cnt2[j] = cnt1[i]-1, cnt2[j]-1
    				cnt1[j], cnt2[i] = cnt1[j]+1, cnt2[i]+1
    				d := 0
    				for k, a := range cnt1 {
    					if a > 0 {
    						d++
    					}
    					if cnt2[k] > 0 {
    						d--
    					}
    				}
    				if d == 0 {
    					return true
    				}
    				cnt1[i], cnt2[j] = cnt1[i]+1, cnt2[j]+1
    				cnt1[j], cnt2[i] = cnt1[j]-1, cnt2[i]-1
    			}
    		}
    	}
    	return false
    }
    
  • function isItPossible(word1: string, word2: string): boolean {
        const cnt1: number[] = Array(26).fill(0);
        const cnt2: number[] = Array(26).fill(0);
        let [x, y] = [0, 0];
    
        for (const c of word1) {
            if (++cnt1[c.charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
                ++x;
            }
        }
    
        for (const c of word2) {
            if (++cnt2[c.charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
                ++y;
            }
        }
    
        for (let i = 0; i < 26; ++i) {
            for (let j = 0; j < 26; ++j) {
                if (cnt1[i] > 0 && cnt2[j] > 0) {
                    if (i === j) {
                        if (x === y) {
                            return true;
                        }
                    } else {
                        const a = x - (cnt1[i] === 1 ? 1 : 0) + (cnt1[j] === 0 ? 1 : 0);
                        const b = y - (cnt2[j] === 1 ? 1 : 0) + (cnt2[i] === 0 ? 1 : 0);
                        if (a === b) {
                            return true;
                        }
                    }
                }
            }
        }
    
        return false;
    }
    
    

All Problems

All Solutions