சரங்களை சம லீட்கோட் தீர்வாக மாற்ற குறைந்தபட்ச பரிமாற்றங்கள்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான்
பேராசை சரம்

சிக்கல் அறிக்கை

உங்களுக்கு இரண்டு வழங்கப்படுகிறது சரங்களை "x" மற்றும் "y" எழுத்துக்களை மட்டுமே கொண்ட சம நீளத்தின் s1 மற்றும் s2. வெவ்வேறு சரங்களுக்கு சொந்தமான எந்த இரண்டு எழுத்துக்களையும் நீங்கள் இடமாற்றம் செய்யலாம்,
உங்கள் பணி சரம் இரண்டையும் சமமாக்குவது. இரண்டு சரங்களையும் சமமாக்குவது சாத்தியமில்லை என்றால் இரு சரங்களையும் சமமாகவோ அல்லது -1 ஆகவோ செய்ய குறைந்தபட்ச இடமாற்றுகளை திரும்பவும்.

உதாரணமாக

#1

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

#2

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

அணுகுமுறை (பேராசை)

சில சரம் குறியீட்டில் இரு சரங்களிலும் உள்ள எழுத்துக்களைப் பார்த்தால், சாத்தியமான 4 ஜோடிகள் மட்டுமே இருப்பதைக் காண்போம் {s1 [i], s2 [i]}: {“x”, ”x”}, {“y , ”Y”}, {“x”, ”y”}, {“y”, ”x”}.
முதல் இரண்டு வகை ஜோடிகளுக்கு s1 [i] s2 [i] க்கு சமம் (இதுதான் நாம் விரும்புகிறோம்), இதுபோன்ற நிகழ்வுகளுக்கு தேவையான இடமாற்றுகளின் எண்ணிக்கை பூஜ்ஜியமாக இருக்கும்.

மீதமுள்ள ஜோடிகளுக்கு நாம் s1 [i] s2 [i] க்கு சமமாக இல்லை, எனவே நாம் இடமாற்று செயல்பாடுகளைப் பயன்படுத்த வேண்டும்.

இதை நாம் இரண்டு வழிகளில் பயன்படுத்தலாம்:

(i) i மற்றும் j (நான் j க்கு சமமாக இல்லை) ஆகிய இரண்டு குறியீடுகளிலும் 3 வது (அல்லது 4 வது) வகை ஜோடி இருந்தால், நாம் s1 [i] ஐ s2 [j] உடன் மாற்றினால், s1 [i] s2 க்கு சமமாக மாறும் [i] (அதாவது s [i] = s2 [i])
மற்றும் s1 [j] s2 [j] (அதாவது s1 [j] = s2 [j]) க்கு சமமாக மாறும், இதன் பொருள் ஒரு நகர்வில் s1 [i] = s2 [i] மற்றும் s1 [j] = s2 [ j].

சரங்களை சம லீட்கோட் தீர்வாக மாற்ற குறைந்தபட்ச பரிமாற்றங்கள்

 

(ii) குறியீட்டு i இல் 3 வது வகை ஜோடி மற்றும் சில குறியீட்டு j இல் 4 வது வகை ஜோடி இருந்தால் (அல்லது நேர்மாறாக): {“x”, ”y”}, {“y”, ”x”}. எனவே, s1 [i] = s2 [i] மற்றும்
s1 [j] = s2 [j] நாம் இரண்டு முறை இடமாற்றம் செய்ய வேண்டும், முதலில் நாம் s1 [i] ஐ s2 [i] உடன் மாற்ற வேண்டும், இப்போது ஜோடிகள் இப்படி இருக்கும்: {“y”, ”x”}, {“y, "எக்ஸ்"}. இப்போது நாம் s1 [i] ஐ s2 [j] உடன் மாற்ற வேண்டும், மேலும் நாம் பெறுவோம்
s1 [i] = s2 [i] மற்றும் s1 [j] = s2 [j].

 

சரங்களை சம லீட்கோட் தீர்வாக மாற்ற குறைந்தபட்ச பரிமாற்றங்கள்

 

(i) வகை செயல்பாடு இரண்டு குறியீடுகளைத் தீர்ப்பதற்கு 1 நகர்வு மட்டுமே எடுக்கும் என்பதைக் காணலாம், எனவே (i) வகை செயல்பாடுகளை எங்களால் முடிந்தவரை செய்ய முயற்சிப்போம். நாம் அனைத்தையும் எளிதாகப் பெறலாம்
ஜோடிகளின் வகைகள். {“X”, ”y”} pair = n1, {“y”, ”x”} pair = n2 ஆகியவற்றின் எண்ணிக்கையைப் பெறுகிறோம்.
வகை 2 இன் 3 ஜோடி ஒரு இடமாற்றத்தில் தீர்வு காணலாம். எனவே n1 ஜோடிகளை நாம் தீர்க்க வேண்டிய மொத்த இடமாற்று n1 / 2 ஆக இருக்கும், n1 ஒற்றைப்படை என்றால் ஒரு ஜோடி தீர்க்கப்படாமல் இருக்கும்.

இதேபோல் n2 க்கும். n1 மற்றும் n2 இரண்டும் ஒற்றைப்படை என்றால், சரிசெய்யப்படாத ஒவ்வொன்றிலும் ஒரு ஜோடி கிடைக்கும், எனவே அவற்றைத் தீர்க்க 2 இடமாற்றுகள் தேவைப்படும் (ii) வகை செயல்பாட்டைப் பயன்படுத்தலாம்.
இல்லையெனில், 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): நாங்கள் எந்த கூடுதல் இடத்தையும் பயன்படுத்தவில்லை.