algoadvance

Leetcode 1790. Check if One String Swap Can Make Strings Equal

Problem Statement

Leetcode Problem 1790: Check if One String Swap Can Make Strings Equal

You are given two strings s1 and s2 of equal length. A string swap is defined as choosing two indices i and j (0-indexed) of a string and swapping the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on any of the strings. Otherwise, return false.

Clarifying Questions

  1. Are s1 and s2 always of equal length?
    • Yes, the problem states that both strings are of equal length.
  2. What is the maximum possible length of the strings?
    • The problem does not specify, but typically, problems do not impose overly large lengths.
  3. Is there any constraint on the characters in the strings?
    • No, the characters can be any valid characters.

Strategy

To solve this problem, the approach can be as follows:

  1. Check if Both Strings are Already Equal:
    • If s1 is equal to s2, we can return true immediately.
  2. Identify Mismatch Indices:
    • Traverse both strings simultaneously and record the indices where the characters differ.
  3. Evaluate the Mismatch Indices:
    • If there are exactly two mismatching positions and swapping the characters at these indices in s1 makes it equal to s2, then return true.
    • For all other cases, return false.

Code

Here is the implementation in C++:

#include <vector>
#include <string>
using namespace std;

bool areAlmostEqual(string s1, string s2) {
    if (s1 == s2) return true;

    vector<int> mismatchIndices;
    for (int i = 0; i < s1.length(); ++i) {
        if (s1[i] != s2[i]) {
            mismatchIndices.push_back(i);
        }
    }

    // There should be exactly 2 mismatch positions
    if (mismatchIndices.size() != 2) return false;

    int i1 = mismatchIndices[0], i2 = mismatchIndices[1];

    // Swap characters at these two positions in s1
    swap(s1[i1], s1[i2]);
    
    // Check if they become equal
    return s1 == s2;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input strings. The reason is that we are performing a single pass to compare the strings and store mismatched indices, and another very small constant-time operation to check and swap characters if needed. This makes the operation as efficient as possible for this problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI