{x}
blog image

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.

Solution Explanation: Check if One String Swap Can Make Strings Equal

This problem asks whether we can make two strings equal by performing at most one swap on exactly one of the strings. The optimal solution leverages counting to efficiently determine this.

Approach: Counting Differences

The core idea is to count the number of positions where the two strings differ. There are only three possibilities:

  1. Zero differences: The strings are already equal, so we return true.
  2. Two differences: If there are exactly two positions where the characters differ, and swapping those characters makes the strings equal, we return true.
  3. More than two differences: We need more than one swap, so we return false.

The algorithm iterates through both strings simultaneously. It keeps track of:

  • cnt: The number of differing character positions.
  • c1, c2: The characters at the differing positions. These are needed to check for a valid swap in the two-difference case.

The algorithm proceeds as follows:

  1. Initialization: cnt is set to 0, and c1 and c2 are initialized to null characters (or 0 in some languages).

  2. Iteration: The algorithm iterates through the strings, comparing characters at the same index.

  3. Difference Encountered: If characters at the current index differ:

    • Increment cnt.
    • Check for invalid scenarios:
      • If cnt exceeds 2, it's impossible to make the strings equal with one swap, so return false.
      • If cnt is 2, and the characters at the current differing positions (a and b) don't match the previously recorded differing characters (c2 and c1), then a single swap won't suffice. Return false.
    • Record the differing characters: c1 and c2 store the current differing characters.

  4. Post-Iteration: After the loop, if cnt is not equal to 1, it means either zero differences (already equal) or two differences (possibly equal with one swap). Therefore, return true. If cnt is 1, it means a single character needs to be swapped; this isn't allowed.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the strings. We iterate through the strings once.
  • Space Complexity: O(1). We use a constant amount of extra space to store cnt, c1, and c2.

Code Examples (Multiple Languages)

The provided code examples in Python, Java, C++, Go, TypeScript, Rust, and C all implement this approach. They differ slightly in syntax but share the same core logic. The Rust example uses a slightly different, but equally efficient method involving byte arrays and indexing the differing positions. This is for demonstration purposes to highlight that there are different ways to solve this, and the choice of method is mostly stylistic in this case.

The core logic of counting the differences and checking for the valid swap condition remains the same across all languages. This efficient approach ensures that the solution performs well even with large input strings.