#1790

Easy

LeetCode Problem Workspace

Check if One String Swap Can Make Strings Equal

Check if one string swap can make two equal strings using hash table and string counting methods.

Problem Statement

You are given two strings, s1 and s2, both of equal length. A string swap operation consists of choosing two indices in one string and swapping the characters at those positions. You need to determine if it is possible to make both strings equal by performing at most one swap on exactly one of the strings. Return true if it is possible; otherwise, return false.

For example, with s1 = 'bank' and s2 = 'kanb', swapping the first and last characters of s2 will transform it into s1. If there are no mismatches or exactly two mismatches between the two strings, it is possible to make them equal with one swap.

Examples

Example 1

Input: s1 = "bank", s2 = "kanb"

Output: true

For example, swap the first character with the last character of s2 to make "bank".

Example 2

Input: s1 = "attack", s2 = "defend"

Output: false

It is impossible to make them equal with one string swap.

Example 3

Input: s1 = "kelb", s2 = "kelb"

Output: true

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 Approach

Count Character Mismatches

The first step is to identify positions where s1 and s2 differ. If the number of mismatched positions is not 0 or 2, immediately return false since a swap would not be enough to make the strings equal.

Validate the Swap

If there are exactly two mismatched positions, check if swapping the characters at those positions in s2 will result in a string equal to s1. If so, return true.

Handle Identical Strings

If the two strings are already equal (i.e., no mismatches), return true immediately since no swap is required.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity is O(N) due to iterating through the strings to find mismatched positions. The space complexity is O(1), as no additional space is needed beyond a few variables to track the positions of mismatches.

What Interviewers Usually Probe

The candidate should efficiently identify mismatched character positions.
The candidate should recognize the importance of string length and how to handle identical strings directly.
The candidate should avoid unnecessary operations, focusing on counting mismatches and validating potential swaps.

Common Pitfalls or Variants

Common pitfalls

Confusing the number of mismatches, which must be 0 or 2 for a valid swap.
Not checking if swapping characters at mismatched positions results in the strings becoming equal.
Failing to handle the case where the strings are already equal.

Follow-up variants

Handling cases with different character sets, not just lowercase letters.
Considering cases with larger strings where performance may be more important.
Handling strings with more complex structures or patterns beyond simple swaps.

FAQ

What is the primary technique to solve the 'Check if One String Swap Can Make Strings Equal' problem?

The primary technique involves counting the mismatched character positions between the two strings and checking if exactly two mismatches exist, then verifying if swapping those characters will make the strings equal.

What happens if the two strings are already equal in the 'Check if One String Swap Can Make Strings Equal' problem?

If the strings are already equal, no swap is needed, and the answer is true immediately.

How does the mismatch counting strategy help in solving the problem?

Counting mismatched positions helps quickly determine if it's even possible to make the strings equal with one swap. If the number of mismatches is not 0 or 2, it's impossible to make the strings equal with one swap.

What is the time complexity of the 'Check if One String Swap Can Make Strings Equal' problem?

The time complexity is O(N) because we iterate through both strings to identify mismatches, where N is the length of the strings.

What should be done if the number of mismatched positions is more than 2?

If there are more than two mismatched positions, it is impossible to make the strings equal with just one swap, so the answer should be false.

terminal

Solution

Solution 1: Counting

We use a variable $cnt$ to record the number of characters at the same position in the two strings that are different. If the two strings meet the requirements of the problem, then $cnt$ must be $0$ or $2$. We also use two character variables $c1$ and $c2$ to record the characters that are different at the same position in the two strings.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        cnt = 0
        c1 = c2 = None
        for a, b in zip(s1, s2):
            if a != b:
                cnt += 1
                if cnt > 2 or (cnt == 2 and (a != c2 or b != c1)):
                    return False
                c1, c2 = a, b
        return cnt != 1

Continue Practicing

#1781 sum of beauty of all substrings #1737 change minimum characters to satisfy one of three conditions #1876 substrings of size three with distinct characters