859. Buddy Strings

EasyHash TableString
Leetcode Link

Problem Description

The problem provides two strings, s and goal, and asks to determine if it's possible to make them equal by performing exactly one swap of two characters within the string s. Swapping characters involves taking any two positions i and j in the string (where i is different from j) and exchanging the characters at these positions. The goal is to return true if s can be made equal to goal after one such swap, otherwise false.

Intuition

To solve this problem, we first address some basic checks before we move on to character swaps:

  1. Length Check: If the lengths of s and goal aren't the same, it's impossible for one to become the other with a single swap.
  2. Character Frequency Check: If s and goal don't have the same frequency of characters, one cannot become the other, as a single swap doesn't affect the frequency of characters.

After these initial checks, we look for the differences between s and goal:

  • Exact 2 Differences: If there are precisely two positions at which s and goal differ, these could potentially be the two characters we need to swap to make the strings equal. For instance, if s = "ab" and goal = "ba", swapping these two characters would make the strings equal.
  • Zero Differences with Duplicates: If there are no differences, we need at least one character in s that occurs more than once. This way, swapping the duplicates won't alter the string but will satisfy the condition of making a swap. For example, if s = "aa" and goal = "aa", we can swap the two 'a's to meet the requirement.

The solution returns true if either condition is fulfilled - a single swap can rectify exactly 2 differences, or no differences exist and at least one character has a duplicate in s. Otherwise, it returns false.

Solution Approach

The implementation of the solution adheres to the intuition described earlier and uses a couple of steps to determine if we can swap two letters in the string s to match goal. Here's how the solution is accomplished:

  1. Length Check:

    • First, we compare the lengths of s and goal using len(s) and len(goal). If they are different, we immediately return False.
  2. Character Frequency Check:

    • Two Counter objects from the collections module are created, one for each string. The Counter objects cnt1 and cnt2 count the frequency of each character in s and goal, respectively.
    • We then compare these Counter objects. If they are not equal, it means that s and goal have different sets of characters or different character frequencies, so we return False.
  3. Differing Characters:

    • We iterate through s and goal concurrently, checking for characters at the same indices that are not equal. This is done using a comprehension expression that checks s[i] != goal[i] for each i from 0 to n-1.
    • We sum the total number of differences found, and if the sum is exactly 2, it implies there is a pair of characters that can be swapped to make s equal to goal.
  4. Zero Differences with Duplicates:

    • If there are no differences (diff == 0), we check if any character in s has a count greater than 1 using any(v > 1 for v in cnt1.values()). This would mean that there is at least one duplicate character that can be swapped.
  5. Return Value:

    • The function returns True if the sum of differing characters diff is exactly 2 or if there is no difference and there is at least one duplicate character. Otherwise, it returns False.

The overall solution makes use of Python's dictionary properties for quick character frequency checks, and the efficiency of set operations for comparing the two Counter objects. The integration of these checks allows the function to quickly determine whether a single swap can equate two strings, making the solution both concise and effective.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example Walkthrough

Let's consider a small example to illustrate the solution approach using the strings s = "xy" and goal = "yx". We want to determine if making one swap in s can make it equal to goal.

Step 1: Length Check
len(s) == len(goal)
Both strings have the same length of 2 characters.

Step 2: Character Frequency Check
Counter(s) produces Counter({'x': 1, 'y': 1}),
Counter(goal) produces Counter({'y': 1, 'x': 1}).
Comparing these counts, we see they match, which means s and goal have the same characters with the same frequency.

Step 3: Differing Characters
As s[0] != goal[0] ('x' != 'y') and s[1] != goal[1] ('y' != 'x'),
we have exactly two positions where s and goal differ.

Step 4: Zero Differences with Duplicates
This step is only relevant if there were no differences identified in the earlier step. As we have found two differing characters, this step can be skipped.

Step 5: Return Value
Since there are exactly two differences, we can swap the characters 'x' and 'y' in string s to make it equal to goal.
Thus, the function should return True.

Applying these steps to our example s = "xy" and goal = "yx" confirms that the solution approach correctly yields a True result, as a single swap is indeed sufficient to make s equal to goal.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def buddyStrings(self, a: str, b: str) -> bool:
5        # Lengths of both strings
6        len_a, len_b = len(a), len(b)
7      
8        # If lengths are not equal, they cannot be buddy strings
9        if len_a != len_b:
10            return False
11      
12        # Count characters in both strings
13        counter_a, counter_b = Counter(a), Counter(b)
14      
15        # If character counts are not the same, then it's not a simple swap case
16        if counter_a != counter_b:
17            return False
18      
19        # Count the number of positions where the two strings differ
20        difference_count = sum(1 for i in range(len_a) if a[i] != b[i])
21      
22        # Return True if there are exactly two differences
23        # (which can be swapped to make the strings equal)
24        # Or if there's no difference and there are duplicate characters in the string
25        # (which can be swapped with each other while keeping the string the same)
26        return difference_count == 2 or (difference_count == 0 and any(value > 1 for value in counter_a.values()))
27
1class Solution {
2    public boolean buddyStrings(String s, String goal) {
3        int lengthS = s.length(), lengthGoal = goal.length();
4      
5        // If the lengths are not equal, they can't be buddy strings
6        if (lengthS != lengthGoal) {
7            return false;
8        }
9      
10        // If there are differences in characters, we will count them
11        int differences = 0;
12      
13        // Arrays to count occurrences of each character in s and goal
14        int[] charCountS = new int[26];
15        int[] charCountGoal = new int[26];
16      
17        for (int i = 0; i < lengthGoal; ++i) {
18            int charS = s.charAt(i), charGoal = goal.charAt(i);
19          
20            // Increment character counts
21            ++charCountS[charS - 'a'];
22            ++charCountGoal[charGoal - 'a'];
23          
24            // If characters at this position differ, increment differences
25            if (charS != charGoal) {
26                ++differences;
27            }
28        }
29      
30        // To track if we find any character that occurs more than once
31        boolean duplicateCharFound = false;
32      
33        for (int i = 0; i < 26; ++i) {
34            // If character counts differ, they can't be buddy strings
35            if (charCountS[i] != charCountGoal[i]) {
36                return false;
37            }
38          
39            // Check if there's any character that occurs more than once
40            if (charCountS[i] > 1) {
41                duplicateCharFound = true;
42            }
43        }
44      
45        // The strings can be buddy strings if there are exactly two differences
46        // or no differences but at least one duplicate character in either string
47        return differences == 2 || (differences == 0 && duplicateCharFound);
48    }
49}
50
1class Solution {
2public:
3    // Define the buddyStrings function to check if two strings can become equal by swapping exactly one pair of characters
4    bool buddyStrings(string sInput, string goalInput) {
5        int lengthS = sInput.size(), lengthGoal = goalInput.size();
6        // String lengths must match, otherwise it is not possible to swap just one pair
7        if (lengthS != lengthGoal) return false;
8      
9        // Counter to keep track of differences
10        int diffCounter = 0;
11        // Counters to store frequency of characters in both strings
12        vector<int> freqS(26, 0);
13        vector<int> freqGoal(26, 0);
14      
15        // Iterate through both strings to fill freq arrays and count differences
16        for (int i = 0; i < lengthGoal; ++i) {
17            ++freqS[sInput[i] - 'a'];
18            ++freqGoal[goalInput[i] - 'a'];
19            if (sInput[i] != goalInput[i]) ++diffCounter; // Increment diffCounter when characters are not same
20        }
21      
22        // Duplicate found flag, initially false
23        bool hasDuplicate = false;
24        // Check if the strings have different frequency of any character
25        for (int i = 0; i < 26; ++i) {
26            if (freqS[i] != freqGoal[i]) return false; // Frequencies must match for a valid swap
27            if (freqS[i] > 1) hasDuplicate = true;     // If any character occurs more than once, we can potentially swap duplicates
28        }
29      
30        // Valid buddy strings have either:
31        // 2 differences (swap those and strings become equal)
32        // No differences but at least one duplicate character (swap duplicates and strings remain equal)
33        return diffCounter == 2 || (diffCounter == 0 && hasDuplicate);
34    }
35};
36
1function buddyStrings(inputString: string, goalString: string): boolean {
2    // Lengths of the input strings
3    const inputLength = inputString.length;
4    const goalLength = goalString.length;
5
6    // If lengths are not equal, strings cannot be buddy strings
7    if (inputLength !== goalLength) {
8        return false;
9    }
10
11    // Arrays to hold character counts for each string
12    const charCountInput = new Array(26).fill(0);
13    const charCountGoal = new Array(26).fill(0);
14
15    // Variable to count the number of positions where characters differ
16    let differences = 0;
17
18    // Iterate over the strings and populate character counts
19    for (let i = 0; i < goalLength; ++i) {
20        charCountInput[inputString.charCodeAt(i) - 'a'.charCodeAt(0)]++;
21        charCountGoal[goalString.charCodeAt(i) - 'a'.charCodeAt(0)]++;
22
23        // If characters at the same position differ, increment differences
24        if (inputString[i] !== goalString[i]) {
25            ++differences;
26        }
27    }
28
29    // Compare character counts for both strings
30    for (let i = 0; i < 26; ++i) {
31        if (charCountInput[i] !== charCountGoal[i]) {
32            // If counts do not match, strings cannot be buddy strings
33            return false;
34        }
35    }
36
37    // Return true if there are exactly two differences or no differences but at least one character with more than one occurrence
38    return differences === 2 || (differences === 0 && charCountInput.some(count => count > 1));
39}
40

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by several factors:

  1. The length comparison of s and goal strings which takes O(1) time since length can be checked in constant time in Python.
  2. The construction of Counter objects for s and goal is O(m) and O(n) respectively, where m and n are the lengths of the strings. Since m is equal to n, it simplifies to O(n).
  3. The comparison of the two Counter objects is O(n) because it involves comparing the count of each unique character from both strings.
  4. The calculation of diff, which involves iterating through both strings and comparing characters, is O(n).

Since all these steps are sequential, the overall time complexity is O(n) + O(n) + O(n) + O(n) = O(n), where n is the length of the input strings.

Space Complexity

The space complexity is based on the additional space required by the algorithm which is primarily due to the Counter objects:

  1. Two Counter objects for s and goal, each of which will have at most k unique characters where k is the size of the character set used in the strings. The space complexity for this part is O(k).
  2. The additional space for the variable diff is negligible, O(1).

If we assume a fixed character set (like the ASCII set), k could be considered constant and the complexity is O(1) regarding the character set. However, the more precise way to describe it would be O(k) based on the size of the character set.

Therefore, the total space complexity of the algorithm can be expressed as O(k).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄