സ്ട്രിംഗുകൾക്ക് തുല്യമായ ലീറ്റ്കോഡ് പരിഹാരം ഉണ്ടാക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ സ്വാപ്പുകൾ


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ
അത്യാഗ്രഹം സ്ട്രിംഗ്

പ്രശ്നം പ്രസ്താവന

നിങ്ങൾക്ക് രണ്ട് നൽകിയിരിക്കുന്നു സ്ട്രിംഗുകൾ “x”, “y” എന്നീ അക്ഷരങ്ങൾ അടങ്ങിയ തുല്യ നീളമുള്ള s1, s2 എന്നിവ. വ്യത്യസ്ത സ്ട്രിംഗുകളിലുള്ള രണ്ട് പ്രതീകങ്ങളും നിങ്ങൾക്ക് സ്വാപ്പ് ചെയ്യാൻ കഴിയും,
സ്ട്രിംഗ് രണ്ടും തുല്യമാക്കുക എന്നതാണ് നിങ്ങളുടെ ചുമതല. രണ്ട് സ്ട്രിംഗുകളും തുല്യമാക്കുക എന്നത് അസാധ്യമാണെങ്കിൽ രണ്ട് സ്ട്രിംഗുകളും തുല്യമോ -1 ആക്കുന്നതിനോ ആവശ്യമായ കുറഞ്ഞ സ്വാപ്പുകളുടെ എണ്ണം നൽകുക.

ഉദാഹരണം

#1

s1 = "xx", s2 = "yy"
1

#2

s1 = "xy", s2 = "yx"
2

സമീപനം (അത്യാഗ്രഹം)

ചില ith സൂചികയിലെ രണ്ട് സ്ട്രിംഗുകളിലെയും പ്രതീകങ്ങൾ പരിശോധിച്ചാൽ, സാധ്യമായ 4 ജോഡികൾ മാത്രമേ ഉള്ളൂ എന്ന് നമുക്ക് കാണാം {s1 [i], s2 [i]}: {“x”, ”x”}, {“y , ”Y”}, {“x”, ”y”}, {“y”, ”x”}.
ആദ്യത്തെ രണ്ട് തരം ജോഡികൾക്ക് s1 [i] s2 [i] ന് തുല്യമാണ് (ഇതാണ് ഞങ്ങൾക്ക് വേണ്ടത്), ആവശ്യമായ സ്വാപ്പുകളുടെ എണ്ണം അത്തരം സന്ദർഭങ്ങളിൽ പൂജ്യമായിരിക്കും.

ബാക്കിയുള്ള ജോഡികൾക്ക് s1 [i] s2 [i] ന് തുല്യമല്ല, അതിനാൽ ഞങ്ങൾ സ്വാപ്പ് പ്രവർത്തനങ്ങൾ ഉപയോഗിക്കേണ്ടതുണ്ട്.

നമുക്ക് ഇത് രണ്ട് തരത്തിൽ ഉപയോഗിക്കാം:

(i) i, j എന്നീ രണ്ട് സൂചികകളിലും നമുക്ക് മൂന്നാമത്തെ (അല്ലെങ്കിൽ നാലാമത്തെ) ജോഡി ഉണ്ടെങ്കിൽ (i j ന് തുല്യമല്ല), നമ്മൾ s3 [i] നെ s4 [j] ഉപയോഗിച്ച് സ്വാപ്പ് ചെയ്താൽ s1 [i] s2 ന് തുല്യമാകും [i] (അതായത് s [i] = s1 [i])
s1 [j] s2 [j] (അതായത് s1 [j] = s2 [j]) ന് തുല്യമാകും, ഇതിനർത്ഥം ഒരു നീക്കത്തിലൂടെ s1 [i] = s2 [i], s1 [j] = s2 [ j].

സ്ട്രിംഗുകൾക്ക് തുല്യമായ ലീറ്റ്കോഡ് പരിഹാരം ഉണ്ടാക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ സ്വാപ്പുകൾ

 

. അതിനാൽ, s3 [i] = s4 [i] ഉം
s1 [j] = s2 [j] നമുക്ക് രണ്ടുതവണ സ്വാപ്പ് ചെയ്യേണ്ടതുണ്ട്, ആദ്യം നമ്മൾ s1 [i] ഉപയോഗിച്ച് s2 [i] ഉപയോഗിച്ച് സ്വാപ്പ് ചെയ്യേണ്ടതുണ്ട്, ഇപ്പോൾ ജോഡികൾ ഇതുപോലെ കാണപ്പെടും: y “y”, ”x”}, {“y, ”X”}. ഇപ്പോൾ നമുക്ക് s1 [j] ഉപയോഗിച്ച് s2 [i] സ്വാപ്പ് ചെയ്യേണ്ടതുണ്ട്, നമുക്ക് ലഭിക്കും
s1 [i] = s2 [i], s1 [j] = s2 [j].

 

സ്ട്രിംഗുകൾക്ക് തുല്യമായ ലീറ്റ്കോഡ് പരിഹാരം ഉണ്ടാക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ സ്വാപ്പുകൾ

 

(i) തരം പ്രവർത്തനം രണ്ട് സൂചികകൾ പരിഹരിക്കുന്നതിന് ഒരു നീക്കം മാത്രമേ എടുക്കൂ, അതിനാൽ (i) ടൈപ്പ് പ്രവർത്തനങ്ങൾ ചെയ്യാൻ കഴിയുന്നത്ര ശ്രമിക്കും. നമുക്ക് എല്ലാവരുടെയും എണ്ണം എളുപ്പത്തിൽ നേടാനാകും
ജോഡികളുടെ തരങ്ങൾ. നമുക്ക് {“x”, ”y”} pair = n1, {“y”, ”x”} pair = n2 എന്നിവയുടെ എണ്ണം ലഭിക്കുന്നുവെന്ന് പറയാം.
ടൈപ്പ് 2 ന്റെ 3 ജോഡി നമുക്ക് ഒരു സ്വാപ്പിൽ പരിഹരിക്കാനാകും. അതിനാൽ നമുക്ക് n1 ജോഡികൾ‌ തീർപ്പാക്കേണ്ട മൊത്തം സ്വാപ്പ് n1 / 2 ആയിരിക്കും, n1 വിചിത്രമാണെങ്കിൽ‌ ഒരു ജോഡി പരിഹരിക്കപ്പെടാതെ തുടരും.

അതുപോലെ n2 നും. n1, n2 എന്നിവ രണ്ടും വിചിത്രമാണെങ്കിൽ, പരിഹരിക്കപ്പെടാത്ത ഓരോ ജോഡികളും നമുക്ക് ലഭിക്കും, അതിനാൽ (ii) ടൈപ്പ് ഓപ്പറേഷൻ ഉപയോഗിച്ച് അവ പരിഹരിക്കാൻ 2 സ്വാപ്പുകൾ ആവശ്യമാണ്.
അല്ലാത്തപക്ഷം, n1, n2 എന്നിവയുടെ തുല്യത തുല്യമല്ലെങ്കിൽ (അതായത് n1 വിചിത്രവും n2 തുല്യവുമാണ്) അപ്പോൾ നമുക്ക് പരിഹരിക്കപ്പെടാത്ത ഒരു ജോഡി ലഭിക്കും,
അത്തരം സന്ദർഭങ്ങളിൽ, സ്ട്രിംഗുകളെ തുല്യമാക്കുന്നത് അസാധ്യമായിരിക്കും.

നടപ്പിലാക്കൽ

സ്ട്രിംഗുകൾക്ക് തുല്യമായ ലീറ്റ്കോഡ് പരിഹാരം ഉണ്ടാക്കുന്നതിനുള്ള മിനിമം സ്വാപ്പുകൾക്കായുള്ള സി ++ പ്രോഗ്രാം

#include<bits/stdc++.h>
using namespace std;
int minimumSwap(string s1, string s2) 
{
    int xy_count=0,//count of {x,y} pairs
    yx_count=0,//count of {y,x} pairs
    n=s1.length();
    for(int i=0;i<n;i++)
    {
        if(s1[i]!=s2[i])
        {
            if(s1[i]=='x') xy_count++;
            else yx_count++;
        }
    }
    if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+(xy_count%2==1);//if parity of count of xy pair and yx pair is same 
    else return -1;
}

int main()
{
    string s1="xxxyy",s2="yyxxx";
    cout<<minimumSwap(s1,s2);
    return 0;
}
2

സ്ട്രിംഗുകൾക്ക് തുല്യമായ ലീറ്റ്കോഡ് പരിഹാരം ഉണ്ടാക്കുന്നതിനുള്ള മിനിമം സ്വാപ്പുകൾക്കായുള്ള ജാവ പ്രോഗ്രാം

class Rextester{
    
      public static int minimumSwap(String s1, String s2) 
      {
         
        int xy_count=0,//count of {x,y} pairs
        yx_count=0,//count of {y,x} pairs
        n=s1.length();
        for(int i=0;i<n;i++)
        {
            if(s1.charAt(i)!=s2.charAt(i))
            {
                if(s1.charAt(i)=='x') xy_count++;
                else yx_count++;
            }
        }

        //if parity of count of xy pair and yx pair is same 
        if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+((xy_count%2==1)?1:0);
        else return -1;
    }
    
    public static void main(String args[])
    {
       	String s1="xxxyy",s2="yyxxx";
        System.out.println(minimumSwap(s1,s2) );
    }
}
2

സ്ട്രിംഗുകൾക്ക് തുല്യമായ ലീറ്റ്കോഡ് പരിഹാരം ഉണ്ടാക്കുന്നതിനുള്ള മിനിമം സ്വാപ്പുകൾക്കായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n): ഇവിടെ n എന്നത് സ്ട്രിംഗിന്റെ നീളം. ഞങ്ങൾ രണ്ട് സ്ട്രിംഗും ഒരു തവണ മാത്രം ആവർത്തിക്കുന്നതിനാൽ, സമയ സങ്കീർണ്ണത O (n) ആയിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1): ഞങ്ങൾ അധിക സ്ഥലമൊന്നും ഉപയോഗിക്കുന്നില്ല.