[LeetCode in Swift] Buddy Strings

Hello this is Noobie! 👋

I’m starting a new blog series called LeetCode in Swift, where I solve LeetCode challenges in Swift, as I am in the middle of job hunting process and I need to prepare for possible upcoming coding interview.

This question is a Easy difficulty in LeetCode and shows history of being asked this question from interviews at DoorDash, and Square for 6–12 months of experience interviewees.

Disclaimer: I am not an experienced developer nor I have a Computer Science education background. My solution may not be the most efficient or effective approach in solving the problem. The reason why I am writing this in blog series is to help these logics, algorithms and approach to stick into my head, and to possibly help absolute beginners who is also facing similar problems.

Today’s challenge: Buddy Strings

Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, 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 s[i] and s[j].

• For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= s.length, goal.length <= 2 * 104
• s and goal consist of lowercase letters.

Think of today’s solution as an extension of the question I solved last week. If you haven’t already read my previous blog, please read the previous blog first as it will help you understand this solution better!

Approach and Thought Process

To solve this problem efficiently, we need to carefully analyze the requirements and constraints. Here’s how we can approach the problem:

1. Length Check: Since we need to make both strings equal by performing at most one string swap, the first step is to check if they have the same length. If not, we can return false immediately because swapping two characters in s cannot make s longer or shorter.
2. Equality Check: Next, we check if s and goal are already equal. If they are, the question allows us to swap two identical characters. However, this is only possible if s (and therefore goal) contains at least one duplicate character. We can check this by converting s to a set, which removes duplicates, and checking if the count has decreased. If s contains duplicates, we can return true; otherwise, we return false.
3. Differences Analysis: If s and goal are not equal, we need to analyze the differences between the two strings. We are allowed to perform exactly one string swap.
4. Single Swap Possibility: If there are more than two differences between s and goal, it is impossible to make the strings equal with a single swap. We can return false in this case.
5. Single Swap Validation: If there are exactly two differences between s and goal, we can potentially make the strings equal with a single swap.
6. Implementing the Solution: Based on our analysis, we can implement a solution that checks for these conditions and returns the appropriate result.

Let’s look into this in more detail, step-by-step approach.

Step 1: Length Check

We should first check to see if s and goal have the same length. If not, we can immediately return false:

if s.count != goal.count {
  return false
}

Step 2: Equality Check

We next check to se if s and goal are equal to each other.

if s == goal {
  return Set(s).count < s.count
}

You will notice here that we used Set here. As per Apple’s documentation, Set is an unordered collection of unique elements. This will help us remove duplicate characters and check if the count of the Set is less than the count of s.

Say we have s and goal equal to a word tomato. We know that there are two duplicate characters t and o. We can Set(s) to remove duplicates, which will result in toma. If the count of the Set is less than the count of s, s contains at least one duplicate character, and we can return true because we can swap the two occurrences of this duplicate character (swap t with a duplicate character of another t, or o with a duplicate character of another o).

Step 3 & 4: Differences Analysis & Single Swap Possibility

If s and goal are not equal, we compute the pairs of corresponding characters in s and goal that are different. We use the zip method to pair up the characters in s and goal and the filter method to remove the pairs where the characters are the same.

let diffs = zip(s, goal).filter { $0 != $1 }

Looks familiar right? Yes, we can use same approach as we did from the last solution as we are now only dealing with cases as we are assuming that they both have same length and are not equal to each other.

Step 5: Single Swap Validation

Finally, if there are exactly two pairs in diffs, and these pairs are the same but in reverse order, we return true because we can make s equal to goal by swapping the characters in these two pairs. Otherwise, we return false because it’s not possible to make s equal to goal with a single swap.

return diffs.count == 2 && diffs[0] == (diffs[1].1, diffs[1].0)

This process effectively breaks down the problem into smaller, manageable parts, allowing us to come up with an efficient and understandable solution.

Step 6: Implementing the Solution

Final code will look like this (left some comments to help understanding the code):

class Solution {
    func buddyStrings(_ s: String, _ goal: String) -> Bool {
        
        // If the lengths of the two strings are different, it's impossible to make them equal by swapping characters in s, so we return false.
        if s.count != goal.count {
            return false
        }

        // Check if string s equals to string goal:
        if s == goal {
            // We check if string s has any duplicate characters by converting it to a set and comparing the counts.
            // If string s contains any duplicates, we can perform a "meaningless" swap (swapping a character with another occurrence of itself) that doesn't change s, so we return true.
            // If all characters in s are unique, any swap would change string s and thus it would no longer equal goal, so we return false.
            return Set(s).count < s.count
            
        } else {
            // If string s does not equal string goal, we find the pairs of corresponding characters in string s and string goal that are different.
            // If there are exactly two such pairs, and these pairs are the same but in reverse order, we can make string s equal to string goal by swapping the two different characters in string s, so we return true.
            // Otherwise, it's not possible to make string s equal to string goal with a single swap, so we return false.
            let diffs = zip(s, goal).filter { $0 != $1 }
            return diffs.count == 2 && diffs[0] == (diffs[1].1, diffs[1].0)
        }
        
    }
}

Let’s give it a go in LeetCode!

Our solutions provided have successfully passed all the tests and was accepted!

Time Complexity

The time complexity of our solution is O(n), where n is the length of s (or goal). This is because we potentially iterate through every character in both s and goal once when creating the diffs array.

Space Complexity

The space complexity of our solution is also O(n) because, in the worst case, diffs can contain every pair of characters from s and goal if all characters are different.

And that wraps up today’s challenge on buddy strings. I hope you found this walk-through helpful and understandable. Remember, practicing problem-solving is key to becoming a better programmer and acing your coding interviews. If you have any feedback or suggestions, feel free to drop a comment.

Happy coding, everyone! 🔥