859. Buddy Strings / 1657. Determine if Two Strings Are Close

페이스북 폰스크린 기출문제, 이 문제는 easy이기 때문에, 관련문제 medium까지 함께 풀이.

859. Buddy Strings

Given two strings A and B of lowercase letters, return true if you can swap two letters in A so the result is equal to B, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at A[i] and A[j]. For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

Input: A = "ab", B = "ba" Output: true Explanation: You can swap A[0] = 'a' and A[1] = 'b' to get "ba", which is equal to B.

Example 2:

Input: A = "ab", B = "ab" Output: false Explanation: The only letters you can swap are A[0] = 'a' and A[1] = 'b', which results in "ba" != B.

Example 3:

Input: A = "aa", B = "aa" Output: true Explanation: You can swap A[0] = 'a' and A[1] = 'a' to get "aa", which is equal to B.

Example 4:

Input: A = "aaaaaaabc", B = "aaaaaaacb" Output: true

Example 5:

Input: A = "", B = "aa" Output: false

Constraints:

0 <= A.length <= 20000
0 <= B.length <= 20000
A and B consist of lowercase letters.

Solution

Approach 1: Enumerate Cases

Intuition

If the characters at the index of i in both strings are identical, i.e. A[i] == B[i], we call the characters at the index i as matched.

If swapping A[i] and A[j] would demonstrate that A and B are buddy strings, then A[i] == B[j] and A[j] == B[i]. That means among the four free variables A[i], A[j], B[i], B[j], there are only two cases: either A[i] == A[j] or not.

Algorithm

Let's work through the cases.

In the case A[i] == A[j] == B[i] == B[j], then the strings A and B are equal. So if A == B, we should check each index i for two matches with the same value.

In the case A[i] == B[j], A[j] == B[i], (A[i] != A[j]), the rest of the indices match. So if A and B have only two unmatched indices (say i and j), we should check that the equalities A[i] == B[j] and A[j] == B[i] hold.

class Solution(object):
    def buddyStrings(self, A, B):
        if len(A) != len(B): return False
        if A == B:
            seen = set()
            for a in A:
                if a in seen:
                    return True
                seen.add(a)
            return False
        else:
            pairs = []
            for a, b in itertools.izip(A, B):
                if a != b:
                    pairs.append((a, b))
                if len(pairs) >= 3: return False
            return len(pairs) == 2 and pairs[0] == pairs[1][::-1]

class Solution:
    def buddyStrings(self, A: str, B: str) -> bool:
        if len(A) != len(B): return False
        if A == B and len(set(A)) < len(A): return True
        dif = [(a, b) for a, b in zip(A, B) if a != b]
        return len(dif) == 2 and dif[0] == dif[1][::-1]

if length differs or set of characters differ, return False directly
if A and B are equal, returns if we have at least 1 repetitive character in the list
if two list have more than 2 indices with different characters, return false
In the end check if the swap can happen

class Solution:
    def buddyStrings(self, A, B):
        if len(A) != len(B) or set(A) != set(B): return False       
        if A == B:
            return len(A) - len(set(A)) >= 1
        else:     
            indices = []
            counter = 0
            for i in range(len(A)):
                if A[i] != B[i]:
                    counter += 1
                    indices.append(i)       
                if counter > 2:
                    return False       
            return A[indices[0]] == B[indices[1]] and A[indices[1]] == B[indices[0]]

Complexity Analysis

Time Complexity: O(N), where N is the length of A and B.
Space Complexity: O(1).

1657. Determine if Two Strings Are Close

leetcode.com/problems/determine-if-two-strings-are-close/

사실은 글자의 빈도수만 같으면 되기 때문에 아래의 코드도 가능.

주의할점은 카운터의 카운터

from collections import Counter

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        return set(word1) == set(word2) and Counter(Counter(word1).values()) == Counter(Counter(word2).values())

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.

Example 1:

Input: word1 = "abc", word2 = "bca" Output: true Explanation: You can attain word2 from word1 in 2 operations. Apply Operation 1: "abc" -> "acb" Apply Operation 1: "acb" -> "bca"

Example 2:

Input: word1 = "a", word2 = "aa" Output: false Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc" Output: true Explanation: You can attain word2 from word1 in 3 operations. Apply Operation 1: "cabbba" -> "caabbb" Apply Operation 2: "caabbb" -> "baaccc" Apply Operation 2: "baaccc" -> "abbccc"

Example 4:

Input: word1 = "cabbba", word2 = "aabbss" Output: false Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.

Constraints:

1 <= word1.length, word2.length <= 105
word1 and word2 contain only lowercase English letters.

Operation 1 allows you to freely reorder the string.

Hide Hint 2

Operation 2 allows you to freely reassign the letters' frequencies.

Solution

Overview

Our aim is to determine if the given 2 strings are close. The problem states that the strings are close if we could perform certain operations on either one string or both strings any number of times and make those strings equal. We could perform the following transformations,

Operation 1 : Swapping any 2 characters (aabc -> acba).

Operation 2 : Exchanging the occurrence of any 2 characters (aabcc -> ccbaa OR abcc -> ccba).

Now, performing these 2 operations for every 2 characters in strings and determining the closeness after every operation would be costly. How can we optimize it?

From the given operations, we could observe that if any 2 strings are close, they always satisfy follow conditions,

Condition 1: Every character that exists in word1 must exist in word2 as well, irrespective of the frequency.

Let's understand this condition with an example. The following figure illustrates the valid transformations of a string uua on applying operations 1 and 2.

In all the transformations of string uua, the character u and a are always present. Thus, if any string is close to uua it must contain the characters u and a.

Condition 2: The frequency of all the characters is always the same. In the above example for string uua, regardless of the operation, following condition always holds :

There exists 1 character that occurs once (frequency = 1) and 1 character that occurs twice (frequency = 2)

The following figure illustrates that all the transformations of uua follows this condition.

Based on these insights, let's implement the solution using different approaches.

Approach 1: Using HashMap

Intuition

As discussed above, we have to check for the following conditions to determine if given strings word1 and word1 are close:

The strings word1 and word2 must have the same characters (Condition 1).

We can build a set that contains the characters in word1 and word2 and check if both sets are equal.
The occurrence or frequency of characters in word1 and word2 must be the same. (Condition 2).

One way to get the frequency of each character in a string is to use a hashmap. We could build a hashmap with each character as a key and it's frequency as a value of hashmap. Now, we have to verify if there are equal number of characters with a particular frequency. For this, we can sort the frequency values in the hashmap and check for equality.

Instead of building a separate set to check for Condition 1, we can only build one hashmap and check if the keys (that represent each character in the string) are present in both maps.

Algorithm

Initialize hashmaps word1Map and word2Map for strings word1 and word2 respectively.
Iterate over each word and build its hashmap where the key is the individual character of the word and value is the frequency of that character.
To check if characters in word1 and word2 are the same, we must check if the key values of hashmaps word1Map and word2Map are the same.
Now, to check the occurrence, we must sort the values of both hashmaps in increasing order and check for equality.

Implementation

Complexity Analysis

Time Complexity: \mathcal{O}(n). We iterate over each word to build the hashmap which would take \mathcal{O}(n) time. Further, we sort the character keys and frequency values of each hashmap. The maximum size of hashmap would be 26, as we store each character a-z only once. In the worst case, all the sort operations would take \mathcal{O}(26 \log 26) time to sort those frequency values. This gives us total time complexity as \mathcal{O}(n).
Space Complexity: \mathcal{O}(1), as the maximum size of each hashmap would be 26, we are using constant extra space.

Approach 2: Using Frequency Array Map

Intuition

We know that the string contains all the lowercase characters (a-z) only. So, instead of using a hashmap to track the frequency of characters, we could build an array of size 26 as a frequency map, where each array element represents a character's frequency (0th index = a, 1st index = b and so on). In order to check if all characters exist in both words, we could simply iterate over the fixed size frequency map.

Algorithm

Build arrays word1Map and word2Map of size 26 to store the frequencies of each character (a-z).
For the first condition, we must check if the characters in word1 and word2 are the same. There could be multiple ways to implement this. One way is to iterate over each frequency map of size 26 and ensure if a character does not exist in word1Map, then it must not exist in word2Map as well and vice versa. If the condition is not satisfied for any of the characters, return false.
For the second condition, we could simply sort the array in increasing order and return true if arrays are equal, otherwise return false.

Implementation

Complexity Analysis

Time Complexity : \mathcal{O}(n), where n is the length of word.

We iterate over words of size n to build the frequency map which takes \mathcal{O}(n). To check if both words have the same characters and frequency, we iterate over a fixed-size array of size 26 which takes constant time. The sort operation on the array also takes constant time, as the array is of size 26.

This gives us time complexity of \mathcal{O}(n) + \mathcal{O}(1) + \mathcal{O}(1) = \mathcal{O}(n)
Space Complexity: \mathcal{O}(1), as we use constant extra space of size 26 to store the frequency map.

Approach 3: Using Bitwise Operation and Frequency Array Map

Intuition

The previous approach iterates over the map of size 26 to check if the word1 and word2 have the same characters (Condition 1). However, there is another efficient way to implement this.

We just want a way to know if a character exists in a word or not. Instead of iterating over a frequency map to check this condition, we could simply store this information in a single integer. This could be done by making use of Bitwise Operators.

We could use a integer \text{wordBit}, where each bit in the \text{wordBit} stores the information about each of the 26 characters (a-z). The rightmost bit represents the character a, the next left bit would represent character b and so on.

A character exists in the word if it's a corresponding bit is set to 1. The following figure illustrates this idea.

To set a bit represented by a character we must use the bitwise OR operator. Example,

\text{wordBit } | \text{ wordBit << 2}, sets the 2^{nd} bit, \text{wordBit} = 100.

\text{wordBit } | \text{ wordBit << 5}, sets the 5^{th} bit, \text{wordBit} = 100100.

It must be noted that this approach works because the size of the integer is 32 bits (In Java and C++) and we only need to 26 bits to store our information.

Algorithm

Build arrays word1Map and word2Map of size 26 to store the frequencies of each character (a-z) as in Approach 2.
For the first condition, we must check if the characters in word1 and word2 are the same. We use word1Bit and word2Bit to store the bit information of word1 and word2 respectively. While building the frequency map, we update the word bits as well to mark the occurrence of a character.
For the second condition, we could simply sort the array in increasing order and return true if arrays are equal, otherwise return false.

Implementation

Complexity Analysis

Time Complexity : \mathcal{O}(n), where n is the length of the word. The complexity is similar to Approach 2.
Space Complexity: \mathcal{O}(1), as we use constant extra space, frequency map of size 26 and word bits of type integer.