Scale Engineer

Check if One String Swap Can Make Strings Equal

Easy
#1637Time: O(N^3). The nested loops run in `O(N^2)` time. Inside the inner loop, `s1.toCharArray()` takes `O(N)`, creating a `new String()` takes `O(N)`, and `equals()` takes `O(N)`. This leads to a total time complexity of `O(N^2 * N) = O(N^3)`.Space: O(N). We use a character array of size `N` to perform the swap inside the loops.1 company
Patterns
Counting
Data structures
Hash TableString
Companies
DoorDash

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically tries every possible single swap on one of the strings (s1) and checks if the result equals the other string (s2). It also handles the case where the strings are already equal, which requires zero swaps.

Algorithm

  • First, handle the base case: if s1 and s2 are already identical, no swap is needed. The condition "at most one swap" is satisfied, so we return true.
  • If they are not equal, we proceed to try one swap. We can use nested loops to pick two distinct indices, i and j, from s1.
  • For each pair of indices (i, j), we create a new string by swapping the characters s1[i] and s1[j].
  • We then compare this newly formed string with s2. If they are equal, we have found a valid single swap, and we can return true.
  • If we iterate through all possible pairs of indices and none of the resulting swaps make s1 equal to s2, it means it's impossible to do so with a single swap. In this case, we return false.

Walkthrough

The core idea is to explore all outcomes of performing exactly one swap on s1.

  1. Check for equality: First, we handle the base case. If s1 and s2 are already identical, no swap is needed. The condition "at most one swap" is satisfied, so we return true.
  2. Generate all swaps: If they are not equal, we proceed to try one swap. We can use nested loops to pick two distinct indices, i and j, from s1.
  3. Swap and Compare: For each pair of indices (i, j), we create a new string by swapping the characters s1[i] and s1[j]. We then compare this newly formed string with s2. If they are equal, we have found a valid single swap, and we can return true.
  4. Return false: If we iterate through all possible pairs of indices and none of the resulting swaps make s1 equal to s2, it means it's impossible to do so with a single swap. In this case, we return false.
class Solution {    public boolean areAlmostEqual(String s1, String s2) {        if (s1.equals(s2)) {            return true;        }        int n = s1.length();        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                char[] s1Chars = s1.toCharArray();                char temp = s1Chars[i];                s1Chars[i] = s1Chars[j];                s1Chars[j] = temp;                String swappedS1 = new String(s1Chars);                if (swappedS1.equals(s2)) {                    return true;                }            }        }        return false;    }}

Complexity

Time

O(N^3). The nested loops run in `O(N^2)` time. Inside the inner loop, `s1.toCharArray()` takes `O(N)`, creating a `new String()` takes `O(N)`, and `equals()` takes `O(N)`. This leads to a total time complexity of `O(N^2 * N) = O(N^3)`.

Space

O(N). We use a character array of size `N` to perform the swap inside the loops.

Trade-offs

Pros

  • Simple and straightforward to understand.

  • Directly models the problem statement by trying all possible swaps.

Cons

  • Highly inefficient due to the cubic time complexity.

  • For larger strings (though not an issue with the given constraints), this would be too slow.

  • It performs many redundant operations.

Solutions

class Solution {public  boolean areAlmostEqual(String s1, String s2) {    int cnt = 0;    char c1 = 0, c2 = 0;    for (int i = 0; i < s1.length(); ++i) {      char a = s1.charAt(i), b = s2.charAt(i);      if (a != b) {        if (++cnt > 2 || (cnt == 2 && (a != c2 || b != c1))) {          return false;        }        c1 = a;        c2 = b;      }    }    return cnt != 1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem