Solution For Check Whether Two Strings Are Almost Equivalent

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.

Step by Step Implementation For Check Whether Two Strings Are Almost Equivalent

We can solve this problem by using a HashMap to keep track of the frequency of each character in each string. Then, we can iterate through the HashMap and check if the frequency of each character in each string is within 1 of each other.

import java.util.HashMap; 
public class Solution { 
public boolean areAlmostEquivalent(String s, String t) { 
// use a HashMap to keep track of the frequency of each character 
HashMap map = new HashMap<>(); 
for (int i = 0; i < s.length(); i++) { 
char c = s.charAt(i); 
map.put(c, map.getOrDefault(c, 0) + 1); 
} 
for (int i = 0; i < t.length(); i++) { 
char c = t.charAt(i); 
map.put(c, map.getOrDefault(c, 0) - 1); 
} 
// iterate through the HashMap and check if the frequency of each character is within 1 
for (char key : map.keySet()) { 
if (map.get(key) != 0 && Math.abs(map.get(key)) != 1) { 
return false; 
} 
} 
return true; 
} 
}

def check_whether_two_strings_are_almost_equivalent(s1, s2):
    # your code here
    return None

var areAlmostEquivalent = function(s, t) {
    // your code here
};

bool check(string s, string t) 
{ 
    // If both strings are of different length 
    if (s.length() != t.length()) 
        return false; 
  
    // To store counts of characters 
    int count1[26] = {0}, count2[26] = {0}; 
  
    // For each character in both strings 
    for (int i = 0; i < s.length();  i++) 
    { 
        // Increment count of characters in 
        // string s 
        count1[s[i]-'a']++; 
  
        // Increment count of characters in 
        // string t 
        count2[t[i]-'a']++; 
    } 
  
    // Count number of characters to be removed 
    int result = 0; 
    for (int i=0; i<26; i++) 
        result += abs(count1[i] - 
                      count2[i]); 
    return (result == 2); 
}

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            string s = "abcd"; 
            string t = "bcda"; 
            bool result = CheckWhetherTwoStringsAreAlmostEquivalent(s, t); 
            Console.WriteLine(result); 
            Console.ReadLine(); 
        } 

        //This method checks whether two strings are almost equivalent. 
        //Two strings are almost equivalent if they only differ in 2 characters or less. 
        public static bool CheckWhetherTwoStringsAreAlmostEquivalent(string s, string t) 
        { 
            //Check for the null and empty strings. 
            if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) 
            { 
                return false; 
            } 

            if (s.Length != t.Length) 
            { 
                return false; 
            } 

            //Create 2 arrays to store the count of characters of each string. 
            int[] s_count = new int[26]; 
            int[] t_count = new int[26]; 

            for (int i = 0; i < s.Length; i++) 
            { 
                s_count[s[i] - 'a']++; 
                t_count[t[i] - 'a']++; 
            } 

            //Compare the 2 arrays and find the count of characters which are not same. 
            int count = 0; 
            for (int i = 0; i < 26; i++) 
            { 
                if (s_count[i] != t_count[i]) 
                { 
                    count++; 
                } 
            } 

            //If the count is 2 or less, then the strings are almost equivalent. 
            if (count <= 2) 
            { 
                return true; 
            } 
            else 
            { 
                return false; 
            } 
        } 
    } 
}