Check Whether Two Strings Are Almost Equivalent - Leetcode Solution

Problem Statement:

Given two strings, s and t, return true if they are almost equivalent.

Two strings s and t are almost equivalent if there exists a permutation of the characters in s such that s can be changed to t by swapping at most one pair of adjacent characters in s.

Example:

Input: s = "bank", t = "kanb" Output: true

Input: s = "attack", t = "defend" Output: false

Approach:

To solve this problem, we can check if the two strings s and t are equal or not. If they are, then obviously we can swap any pair of adjacent characters any number of times, resulting in the same string only. So we return true.

If s and t are not equal, we can again check if their lengths are equal. If not, we return false immediately because no matter how much we swap adjacent characters in s, we cannot obtain t if their lengths are not equal.

If the lengths of s and t are equal, we can iterate through both strings simultaneously and check for the differences. If we find more than one difference, we return false immediately because we can swap at most one pair of adjacent characters.

If we find exactly one difference, we check if we can swap the characters at those indices in s to obtain t. If yes, we return true, else false.

Solution:

Here's the implementation of the above approach:

bool areAlmostEqual(string s, string t) {

int n = s.length(), cnt = 0;
vector<int> pos;

// Check if s and t are equal
if (s == t) return true;

// Check if lengths of s and t are equal
if (n != t.length()) return false;

// Iterate through s and t simultaneously
for (int i = 0; i < n; i++) {
    if (s[i] != t[i]) {
        cnt++; // Increment the count of differences
        
        if (cnt > 2) return false; // More than one difference
        
        pos.push_back(i); // Store the indices of differences
    }
}

// Check if we can swap at most one pair of adjacent characters
if (cnt == 2 && s[pos[0]] == t[pos[1]] && s[pos[1]] == t[pos[0]]) return true;

// Else false
return false;

}

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the strings s and t.

Space Complexity:

The space complexity of this solution is O(1), except for the vector to store the indices of differences, which takes O(2) = O(1) extra space.

1