[LeetCode in Swift] Check if One String Swap Can Make Strings Equal

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 Bloomberg, 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: Check if One String Swap Can Make strings Equal

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Constraints:

• 1 <= s1.length, s2.length <= 100
• s1.length == s2.length
• s1 and s2 consist of only lowercase English letters.

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. Equality Check: Since we need to make both strings equal, the first step is to check if they are already equal. If s1 and s2 are equal, no string swap is needed, and we can return true immediately.
2. Differences Analysis: If s1 and s2 are not equal, we need to analyze the differences between the two strings. We are allowed to perform at most one string swap on exactly one of the strings.
3. Single Swap Possibility: If there are more than two differences between s1 and s2, it is impossible to make the strings equal with a single swap. We can return false in this case.
4. Single Swap Validation: If there are exactly two differences between s1 and s2, we can potentially make the strings equal with a single swap.
5. Implementing the Solution: Based on our analysis, we can implement a solution that checks for these conditions and returns the appropriate result.

Step 1. Equality Check

if s1 == s2 {
  return true
}

First thing that we encounter should be this line. Even if we end up not using it in future, it’s good idea to still write it down as it will remind ourselves that this portion has been taken care of.

Step 2. Differences Analysis

Although there are many ways we can go about this step, I want to show you a quick trick that I use, and it’s by using a filter.

let diffs = zip(s1, s2).filter { $0 != $1 }

What is zip? According to Apple’s documentation, zip creates a sequence of pairs built out of two underlying sequences, and it’s return value is a sequence of tuple pairs, where the elements of each pair are corresponding elements of sequence1 and sequence2.

Think of it this way and this example is only to help better visualize the explanation. Are you familiar with .zip files that we use daily basis? Just as zipping files combines multiple files into a single compressed file, the zip method allows us to combine two sequences, in this case, the characters of s1 and s2, into a sequence of tuples.

Each tuple contains corresponding elements from both sequences. Let’s see it in action to better visualize.

s1 = "bank"
s2 = "kanb"

let diff = zip(s1, s2)
print(diff)

In this example, we are using s1 and s2, “zipping” these two sequences and we print this to see what it looks like. The output will be:

// Output
[("b", "k"), ("a", "a"), ("n", "n"), ("k", "b")]

Notice how first (left) value of the tuple contains each character of s1, and second (right) value of the tuple contains each character of s2?

This means we can use this information to filter out anything that does not match so that we are only left with the ones that does not match. We can do this by using filter:

let diffs = zip(s1, s2).filter { $0 != $1 }

Extending from the previous example, this will give us the output:

// Output
[("b", "k"), ("k", "b")]

It filters out tuples where the corresponding characters from s1 and s2 are not equal. In this case, the resulting array contains two tuples (“b”, “k”) and (“k”, “b”). These tuples represent the differing characters between s1 and s2.

Why is this significant? Since we now know the difference and stored them in an array, we can use this information to perform validation.

3. Single Swap Possibility

We already mentioned that if the strings are equal to each other (in other words, if the array of tuples is empty, which means we didn’t find any difference in characters) we can safely return true.

if s1 == s2 { return true } // This can be removed

// We will replace the validation above with:
return diffs.count == 0

By returning diffs.count == 0, we are basically saying the same exact thing. If the diffs.count == 0, two strings are identical, therefore return true.

4. Single Swap Validation

We need to validate that the diffs.count == 2 as any number below or above 2 will not be considered as a single swap.

return diffs.count == 2

But just because the diffs.count == 2 doesn’t necessarily mean that they will be identical after a single swap. We also need to perform this swap to make sure that they are equal to each other after the swap. You can do it by:

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

We must keep the diffs.count == 2, but also need to make sure that diffs[0], (“b”, “k”) is equal to reciprocal of diffs[1], (diffs[1].1, diffs[1].0).

We are basically switching indexes and validating to see if swapping makes it equal to first tuple: diffs[0]. If they are equal after the swap, than it will return true, otherwise, false.

5. Implementing the Solution

And that’s it! With these two simple lines of code, we are able to perform full validation. Final code will look like this (left some comments to help understanding the code):

class Solution {
    func areAlmostEqual(_ s1: String, _ s2: String) -> Bool {
        // First, we will create a collection of tuples (diffs) where each tuple contains a pair of corresponding characters from s1 and s2 that are not equal to each other.
        let diffs = zip(s1, s2).filter { $0 != $1 }
        
        // If there are no tuples in diffs (i.e., if diffs.count == 0), then s1 and s2 are already equal, and we return true.
        // If there are exactly two tuples in diffs (i.e., if diffs.count == 2), then we check if swapping the characters in the second tuple makes it equal to the first tuple. 
        // If it does, then a single swap in s1 or s2 would make the two strings equal, and we return true.
        // In all other cases, s1 and s2 cannot be made equal with a single swap, so we return false.
        return diffs.count == 0 || (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:

• Constructing the diffs collection takes O(n) time, where n is the length of s1 (or s2) since we need to iterate over both strings once.
• Checking the count of diffs and comparing tuples takes O(1) time since the maximum number of tuples is 2.
• Therefore, the overall time complexity is O(n), where n is the length of s1 (or s2).

Space Complexity:

• The space used by our solution is O(1) since we only store a few variables and tuples.
• Therefore, the space complexity is constant.

We have successfully solved the problem of checking if one string swap can make two strings equal. It’s important to understand the thought process behind problem-solving as it helps us become better programmers and prepares us for coding interviews.

I hope you enjoyed this blog post and found it helpful. If you have any suggestions, feel free to leave a comment. Stay tuned for more LeetCode challenges in Swift!

Happy coding, everyone! 🔥