1790. Check if One String Swap Can Make Strings Equal - Detailed Explanation

Problem Statement

You are given two strings, s1 and s2, of equal length. You are allowed to swap two characters in s1 at most once. Determine if it is possible to make s1 equal to s2 by performing at most one swap. In other words, if the two strings are already equal or can be made equal by swapping exactly one pair of characters in s1, return true; otherwise, return false.

Examples:

1. Example 1:

   • Input: s1 = "bank", s2 = "kanb"
   • Output: true
   • Explanation: By swapping the first and last characters in "bank", you get "kanb", which equals s2.

2. Example 2:

   • Input: s1 = "attack", s2 = "defend"
   • Output: false
   • Explanation: No single swap can transform "attack" into "defend".

3. Example 3:

   • Input: s1 = "kelb", s2 = "kelb"
   • Output: true
   • Explanation: The strings are already equal; hence, no swap is needed.

4. Example 4:

   • Input: s1 = "abcd", s2 = "dcba"
   • Output: false
   • Explanation: More than one swap is required to make the strings equal.

Constraints:

• Both strings have the same length.
• The strings contain only lowercase English letters (or can be assumed to have a valid character set).

Hints Before Solving

• Hint 1: Start by comparing the strings character by character.
• Hint 2: Identify the positions where the two strings differ.
• Hint 3: If there are exactly two differences, check if swapping the two mismatched characters in one string makes the strings equal.
• Hint 4: If the strings are already equal, no swap is needed.

Approaches to Solve the Problem

Approach 1: Count and Compare the Differences (Optimal)

Explanation:

1. Compare the Strings:
   Traverse both strings simultaneously and record the indices where the characters differ.

2. Analyze the Differences:

   • Case 1: If there are no differences (i.e., the strings are already equal), return true.
   • Case 2: If there are exactly two differences, check whether swapping the characters at these indices in s1 would result in s2. Specifically, if the first differing character in s1 equals the second differing character in s2 and vice versa, then the swap would work.
   • Case 3: If there are more than two differences or exactly one difference, then it is impossible to make the strings equal with one swap, so return false.

Visual Walkthrough:

Consider s1 = "bank" and s2 = "kanb":

• Step 1: Compare each character:
  • Index 0: 'b' vs. 'k' → difference.
  • Index 1: 'a' vs. 'a' → match.
  • Index 2: 'n' vs. 'n' → match.
  • Index 3: 'k' vs. 'b' → difference.
• Step 2: Two differences are found at indices 0 and 3.
• Step 3: Check swap conditions:
  • For index 0 and 3: does s1[0] equal s2[3] (i.e. 'b' == 'b') and does s1[3] equal s2[0] (i.e. 'k' == 'k')? Yes.
• Result: Return true.

Approach 2: Brute Force (Less Efficient)

Explanation:

• Idea: Try swapping every possible pair of characters in s1 and check if any swap makes s1 equal to s2.
• Process:
  • If s1 is already equal to s2, return true.
  • Otherwise, iterate over all possible pairs of indices (i, j) in s1, swap the characters at these positions, and check if the modified string equals s2.
  • If a valid swap is found, return true; if no valid swap is found after testing all pairs, return false.

Note: This approach is not optimal because it has a time complexity of O(n²), and it is unnecessary given that the optimal approach can be implemented in O(n).

Code Implementations

Python Implementation