સ્ટ્રિંગ્સ સમાન લેટકોડ સોલ્યુશન બનાવવા માટે ન્યૂનતમ સ્વેપ્સ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન
લોભી શબ્દમાળા

સમસ્યા નિવેદન

તમને બે આપવામાં આવે છે શબ્દમાળાઓ s1 અને s2 સમાન લંબાઈના અક્ષરો ફક્ત "x" અને "y" સમાવે છે. તમે કોઈપણ બે અક્ષરોને અલગ અલગ શબ્દમાળાઓ સાથે જોડાયેલા કરી શકો છો.
તમારું કાર્ય બંને શબ્દમાળાઓને સમાન બનાવવાનું છે. બંને શબ્દમાળાઓને સમાન બનાવવા માટે અથવા -1 ને અવિશ્વિત હોય તો, લઘુતમ સંખ્યામાં સ્વેપ્સ પરત કરો.

ઉદાહરણ

#1

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

#2

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

અભિગમ (લોભી)

જો આપણે કેટલાક આઈથ ઈન્ડેક્સમાં બંને શબ્દમાળાઓના પાત્રો જોઈએ, તો આપણે શોધીશું કે ત્યાં ફક્ત 4 સંભવિત જોડી છે {s1 [i], s2 [i]}: x “x”, ”x”}, {“y , "વાય"}, {"એક્સ", "વાય"}, {"વાય", "એક્સ"}.
પ્રથમ બે પ્રકારનાં જોડીઓ માટે એસ 1 [i] એસ 2 ની બરાબર છે [i] (આ તે છે જે આપણે જોઈએ છે), આવા કેસો માટે જરૂરી સ્વેપ્સની સંખ્યા શૂન્ય હશે.

બાકીની જોડીમાં આપણી પાસે એસ 1 [i] એસ 2 ની સમાન નથી [i], તેથી આપણે સ્વેપ ઓપરેશંસનો ઉપયોગ કરવો જરૂરી છે.

આપણે આનો ઉપયોગ બે રીતે કરી શકીએ:

(i) જો આપણી બંને અનુક્રમણિકા i અને j પર ત્રીજી (અથવા ચોથી) પ્રકારની જોડી છે (હું 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].

સ્ટ્રિંગ્સ સમાન લેટકોડ સોલ્યુશન બનાવવા માટે ન્યૂનતમ સ્વેપ્સ

 

(ii) જો આપણી પાસે અનુક્રમણિકામાં 3 જી પ્રકારની જોડી છે અને કેટલાક અનુક્રમણિકા j (અથવા )લટું) પર જોડીના 4 પ્રકાર છે: {“x”, ”y”}, {“y”, ”x”}. તેથી, એસ 1 બનાવવા માટે [i] = s2 [i] અને
s1 [j] = s2 [j] આપણે બે વાર સ્વેપ કરવાની જરૂર છે, પહેલા આપણે s1 ને અદલાબદલ કરવાની જરૂર છે [i] s2 [i] સાથે, હવે જોડી દેખાશે: {"y", "x"}, {"y, ”X”}. હવે આપણે એસ 1 [i] ને એસ 2 [જે] સાથે સ્વેપ કરવાની જરૂર છે અને અમે મેળવીશું
s1 [i] = s2 [i] અને s1 [j] = s2 [j].

 

સ્ટ્રિંગ્સ સમાન લેટકોડ સોલ્યુશન બનાવવા માટે ન્યૂનતમ સ્વેપ્સ

 

આપણે જોઈ શકીએ કે (i) પ્રકારનું ઓપરેશન બે અનુક્રમણિકાઓને સમાપ્ત કરવા માટે ફક્ત 1 ચાલ લે છે, તેથી આપણે (i) પ્રકારનાં ઓપરેશંસ જેટલા કરી શકીએ તેટલું કરવાનો પ્રયત્ન કરીશું. આપણે સરળતાથી બધાની ગણતરી મેળવી શકીએ છીએ
જોડીનાં પ્રકારો. ચાલો આપણે કહીએ કે આપણને {"x", "y"} જોડીઓ = n1, {"y", "x"} જોડીઓ = n2 ની ગણતરી મળે છે.
આપણે એક સ્વેપમાં ટાઇપ 2 ની 3 જોડીઓ પતાવી શકીએ છીએ. તેથી જો આપણે એન 1 જોડી સમાધાન કરવાની જરૂર હોય ત્યારે કુલ સ્વેપ એન 1/2 હશે, જો એન 1 વિચિત્ર હોય તો એક જોડી અનસેટલે રહેશે.

એ જ રીતે એન 2 માટે. જો એન 1 અને એન 2 બંને વિચિત્ર હોય તો આપણે દરેક અનસેટલ્ડની એક જોડી મેળવીશું જેથી આપણે (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

સ્ટ્રિંગ્સ સમાન લેટકોડ સોલ્યુશન બનાવવા માટે ન્યૂનતમ સ્વેપ્સ માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન): જ્યાં n એ શબ્દમાળાની લંબાઈ છે. જેમ આપણે ફક્ત બંને જ શબ્દમાળાઓ ફરી એકવાર કરી રહ્યા છીએ, તેથી સમય જટિલતા O (n) હશે.

અવકાશ જટિલતા

ઓ (1): અમે કોઈ વધારાની જગ્યાનો ઉપયોગ કરી રહ્યા નથી.