Meta strings (compruebe si dos strings pueden volverse iguales después de un intercambio en una string)

Dadas dos strings, la tarea es verificar si estas strings son strings meta o no. Las strings meta son las strings que se pueden igualar mediante exactamente un intercambio en cualquiera de las strings. Las strings iguales no se consideran aquí como strings Meta.

Ejemplos: 

Input : str1 = "geeks" 
        str2 = "keegs"
Output : Yes
By just swapping 'k' and 'g' in any of string, 
both will become same.

Input : str1 = "rsting"
        str2 = "string
Output : No

Input :  str1 = "Converse"
         str2 = "Conserve"

Preguntado en: Google 

A continuación se muestran los pasos utilizados en el algoritmo. 

1. Compruebe si ambas strings tienen la misma longitud o no, si no, devuelva falso.
2. De lo contrario, comience a comparar ambas strings y cuente el número de caracteres no coincidentes y también almacene el índice de caracteres no coincidentes.
3. Si los caracteres no coincidentes son más de 2, devuelve falso.
4. De lo contrario, verifique si al intercambiar cualquiera de estos dos caracteres en cualquier string, la string sería igual o no.
5. Si es así, devuelve verdadero. De lo contrario, devuelve falso.

Implementación:

// C++ program to check if two strings are meta strings
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if str1 and str2 are meta strings
bool areMetaStrings(string str1, string str2)
{
    int len1 = str1.length();
    int len2 = str2.length();
 
    // Return false if both are not of equal length
    if (len1 != len2)
        return false;
 
    //If strings are equal
    if(str1 == str2){
       set<char>se(str1.begin(), str1.end());
        
       //If there is a character,which occur more than
       //once, we can swap, so that resultant string
       //remains same
       if(se.size() < str1.length()){
           return true;
       }
       return false;   
         
    }
    // To store indexes of previously mismatched
    // characters
    int prev = -1, curr = -1;
 
    int count = 0;
    for (int i=0; i<len1; i++)
    {
        // If current character doesn't match
        if (str1[i] != str2[i])
        {
            // Count number of unmatched character
            count++;
 
            // If unmatched are greater than 2,
            // then return false
            if (count > 2)
                return false;
 
            // Store both unmatched characters of
            // both strings
            prev = curr;
            curr = i;
        }
    }
 
    // Check if previous unmatched of string1
    // is equal to curr unmatched of string2
    // and also check for curr unmatched character,
    // if both are same, then return true
    return (count == 2 &&
            str1[prev] == str2[curr] &&
            str1[curr] == str2[prev]);
}
 
// Driver code
int main()
{
    string str1 = "converse";
    string str2 = "converse";
 
    areMetaStrings(str1,str2) ? cout << "Yes"
                            : cout << "No";
    return 0;
}

// C# program to check if two strings
// are meta strings
using System;
using System.Collections.Generic;
 
class GFG {
     
    // Returns true if str1 and str2
    // are meta strings
    static bool areMetaStrings(String str1,
                                String str2)
    {
        int len1 = str1.Length;
        int len2 = str2.Length;
     
        // Return false if both are not of
        // equal length
        if (len1 != len2)
            return false;
     
        if(str1==str2){
            var c = (new HashSet<char>(str1)).Count;
            if (c<len1){
                return true;
            }
            return false;
             
             
        }
        // To store indexes of previously
        // mismatched characters
        int prev = -1, curr = -1;
     
        int count = 0;
        for (int i = 0; i < len1; i++)
        {
             
            // If current character
            // doesn't match
            if (str1[i] != str2[i])
            {
                 
                // Count number of unmatched
                // character
                count++;
     
                // If unmatched are greater
                // than 2, then return false
                if (count > 2)
                    return false;
     
                // Store both unmatched
                // characters of both strings
                prev = curr;
                curr = i;
            }
        }
     
        // Check if previous unmatched of
        // string1 is equal to curr unmatched
        // of string2 and also check for curr
        // unmatched character, if both are
        // same, then return true
        return (count == 2 &&
                 str1[prev] == str2[curr] &&
                   str1[curr] == str2[prev]);
    }
     
    // Driver method
    public static void Main()
    {
        String str1 = "converse";
        String str2 = "conserve";
     
        Console.WriteLine(
            areMetaStrings(str1,str2)
                       ? "Yes" :"No");
    }
}
 
// This code is contributed by Sam007.

<?php
// php program to check if two strings
// are meta strings
 
// Returns true if str1 and str2 are
// meta strings
function areMetaStrings($str1, $str2)
{
    $len1 = strlen($str1);
    $len2 = strlen($str1);
 
    // Return false if both are not
    // of equal length
    if ($len1 != $len2)
        return false;
 
 
    if($str1 == $str2){
         
        $result = (count_chars($str1, len1));
        if(strlen($result) < $len1){
            return true;
        }
        return false;
    }
    // To store indexes of previously
    // mismatched characters
    $prev = -1; $curr = -1;
 
    $count = 0;
    for ($i = 0; $i < $len1; $i++)
    {
         
        // If current character
        // doesn't match
        if ($str1[$i] != $str2[$i])
        {
             
            // Count number of unmatched
            // character
            $count++;
 
            // If unmatched are greater
            // than 2, then return false
            if ($count > 2)
                return false;
 
            // Store both unmatched
            // characters of both
            // strings
            $prev = $curr;
            $curr = $i;
        }
    }
 
    // Check if previous unmatched of
    // string1 is equal to curr unmatched
    // of string2 and also check for curr
    // unmatched character, if both are
    // same, then return true
    return ($count == 2 &&
            $str1[$prev] == $str2[$curr] &&
            $str1[$curr] == $str2[$prev]);
}
 
// Driver code
    $str1 = "converse";
    $str2 = "conserve";
 
    if(areMetaStrings($str1, $str2))
        echo "Yes";
    else
        echo "No";
 
// This code is contributed by nitin mittal.
?>

# Python program to check if two strings
# are meta strings
 
# Returns true if str1 and str2 are meta strings
def areMetaStrings( str1, str2) :
    len1 = len(str1)
    len2 = len(str2)
       
    # Return false if both are not of equal length
    if (len1 != len2) :
        return False
       
    if str1 == str2:
        char_seen = []
        for char in str1:
            if char not in char_seen:
                char_seen.append(char)
        if len(char_seen) < len(str1):
            return True
        return False       
       
    # To store indexes of previously mismatched
    # characters
    prev = -1
    curr = -1
       
    count = 0
    i = 0
    while i < len1 :
             
        # If current character doesn't match
        if (str1[i] != str2[i] ) :
        
        # Count number of unmatched character
            count = count + 1
       
            # If unmatched are greater than 2,
            # then return false
            if (count > 2) :
                return False
       
            # Store both unmatched characters of
            # both strings
            prev = curr
            curr = i
             
        i = i + 1
       
    # Check if previous unmatched of string1
    # is equal to curr unmatched of string2
    # and also check for curr unmatched character,
    # if both are same, then return true
    return (count == 2 and str1[prev] == str2[curr]
               and str1[curr] == str2[prev])
     
# Driver method
str1 = "converse"
str2 = "converse"
if ( areMetaStrings(str1,str2) ) :
    print("Yes")
else:
    print("No")
     
# This code is contributed by Koulick Sadhu.

<script>
 
      // JavaScript program to check if two strings
      // are meta strings
      // Returns true if str1 and str2
      // are meta strings
      function areMetaStrings(str1, str2) {
        var len1 = str1.length;
        var len2 = str2.length;
 
        // Return false if both are not of
        // equal length
        if (len1 !== len2) return false;
 
        if (str1 === str2) {
          var c = new Set(str1.split(""));
          if (c < len1) {
            return true;
          }
          return false;
        }
        // To store indexes of previously
        // mismatched characters
        var prev = -1,
          curr = -1;
 
        var count = 0;
        for (var i = 0; i < len1; i++) {
          // If current character
          // doesn't match
          if (str1[i] !== str2[i]) {
            // Count number of unmatched
            // character
            count++;
 
            // If unmatched are greater
            // than 2, then return false
            if (count > 2) return false;
 
            // Store both unmatched
            // characters of both strings
            prev = curr;
            curr = i;
          }
        }
 
        // Check if previous unmatched of
        // string1 is equal to curr unmatched
        // of string2 and also check for curr
        // unmatched character, if both are
        // same, then return true
        return (
          count === 2 && str1[prev] === str2[curr] &&
          str1[curr] === str2[prev]
        );
      }
 
      // Driver method
      var str1 = "converse";
      var str2 = "conserve";
 
      document.write(areMetaStrings(str1, str2) ? "Yes" : "No");
       
 </script>

Yes

Complejidad de tiempo: O(N*log N) donde N es la longitud de la string.
Espacio Auxiliar: O(N)

Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.