How do you solve Check if One String Swap Can Make Strings Equal on LeetCode?

Check if One String Swap Can Make Strings Equal (LeetCode #1790) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: If the strings are already equal, no swap is needed.

What is the brute force solution for Check if One String Swap Can Make Strings Equal?

The brute force approach for Check if One String Swap Can Make Strings Equal is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks all possible pairs of indices in one string and swaps them to see if the two strings become equal. This is straightforward but inefficient because it examines every possible swap. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Check if One String Swap Can Make Strings Equal?

Check if One String Swap Can Make Strings Equal uses the following concepts: Hash Table, String, Counting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Check if One String Swap Can Make Strings Equal?

Always consider edge cases, such as strings being equal. Explain your thought process clearly while coding. Use comments to clarify your logic, especially in complex sections.

What are common mistakes when solving Check if One String Swap Can Make Strings Equal?

Not checking if the strings are already equal before proceeding. Failing to handle cases where the number of differing positions is not exactly 2.

#1790

Check if One String Swap Can Make Strings Equal

Easy

Hash TableStringCountingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages the observation that we only need to check the positions where the characters differ between the two strings. If there are exactly two such positions, we can check if swapping those characters makes the strings equal.

⚙️

Algorithm

5 steps

1Step 1: Initialize a list to store indices where s1 and s2 differ.
2Step 2: Iterate through both strings and record the indices of differing characters.
3Step 3: If the number of differing indices is 0, return true (strings are already equal).
4Step 4: If the number of differing indices is not 2, return false (cannot be made equal with one swap).
5Step 5: Check if swapping the characters at the differing indices makes the strings equal.

solution.py12 lines

1# Full working Python code
2
3def canSwap(s1, s2):
4    if s1 == s2:
5        return True
6    diff = []
7    for i in range(len(s1)):
8        if s1[i] != s2[i]:
9            diff.append(i)
10    if len(diff) != 2:
11        return False
12    return s1[diff[0]] == s2[diff[1]] and s1[diff[1]] == s2[diff[0]]

ℹ

Complexity note: The time complexity is O(n) because we only need to make a single pass through the strings to find differing characters. The space complexity is O(n) due to storing the indices of differing characters in a list.

1If the strings are already equal, no swap is needed.
2Only two differing positions can be swapped to make the strings equal.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.