מינימום סוואַפּס צו מאַכן סטרינגס גלייַך לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן
זשעדנע שטריקל

פּראָבלעם סטאַטעמענט

איר זענט צוויי סטרינגס s1 און s2 פון גלייך לענג, בלויז פֿון אותיות "x" און "y". איר קענען ויסבייַטן צוויי אותיות געהערן צו פאַרשידענע סטרינגס,
דיין אַרבעט איז צו מאַכן ביידע די שטריקל גלייַך. צוריקקומען מינימום נומער פון סוואַפּס פארלאנגט צו מאַכן ביידע סטרינגס גלייַך אָדער -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) אויב מיר האָבן 3 (אָדער 4) טיפּ פּאָר ביי ביידע ינדעקסיז i און j (i איז ניט גלייַך צו j), אויב מיר ויסבייַטן 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) אויב מיר האָבן 3 טיפּ פון פּאָר אין אינדעקס i און 4 טיפּ פון פּאָר ביי עטלעכע אינדעקס j (אָדער וויצע ווערסאַ): {“x”, ”y”}, {“y”, “x”}. אַזוי, צו מאַכן ס 1 [איך] = ס 2 [איך] און
s1 [j] = s2 [j] מיר דאַרפֿן צו ויסבייַטן צוויי מאָל, ערשטער מיר דאַרפֿן צו ויסבייַטן s1 [i] מיט s2 [i], איצט די פּאָר וועט זיין ווי: ”רענטגענ”}. איצט מיר דאַרפֿן צו ויסבייַטן s1 [i] מיט s2 [j] און מיר וועלן באַקומען
ס 1 [איך] = ס 2 [איך] און ס 1 [דזש] = ס 2 [דזש].

 

מינימום סוואַפּס צו מאַכן סטרינגס גלייַך לעעטקאָדע סאַלושאַן

 

ווי מיר קענען זען (i) טיפּ אָפּעראַציע נעמט נאָר 1 מאַך צו באַפרייַען צוויי ינדעקסיז, אַזוי מיר וועלן פּרובירן צו מאַכן (i) טיפּ אַפּעריישאַנז ווי פיל ווי מיר קענען. מיר קענען לייכט ציילן אַלע
טייפּס פון פּערז. זאל ס זאָגן מיר באַקומען ציילן פון {“x”, ”y”} פּערז = n1, ציילן פון {“y”, ”x”} פּערז = n2.
מיר קענען פאַרענטפערן 2 פּערז פון טיפּ 3 אין איין ויסבייַטן. אַזוי די גאַנץ ויסבייַטן וואָס מיר דאַרפֿן צו פאַרענטפערן N1 פּערז וועט זיין N1 / 2. אויב N1 איז מאָדנע, וועט איין פּאָר בלייבן ומבאַשלאָסן.

סימילאַרלי פֿאַר נ 2. אויב N1 און N2 ביידע זענען מאָדנע, מיר וועלן באַקומען איין פּאָר פון יעדער ומבאַשלאָסן אַזוי מיר קענען נוצן (ii) טיפּ אָפּעראַציע וואָס ריקווייערז 2 סוואַפּס צו פאַרענטפערן זיי.
אַנדערש, אויב די פּאַריטעט פון n1 און n2 איז נישט די זעלבע (ד"ה n1 איז מאָדנע און n2 איז גלייך), מיר וועלן באַקומען איין פּאָר וואָס איז נישט געזעצט,
אין דעם פאַל, עס וועט זיין אוממעגלעך צו מאַכן די סטרינגס גלייַך.

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם פֿאַר מינימום סוואַפּס צו מאַכן סטרינגס גלייַך לעעטקאָדע סאַלושאַן

#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

Java פּראָגראַם פֿאַר מינימום סוואַפּס צו מאַכן סטרינגס גלייַך לעעטקאָדע סאַלושאַן

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): וואו n איז די לענג פון די שטריקל. זינט מיר יטערירן ביידע די שטריקל נאָר אַמאָל, דערפאר די צייט קאַמפּלעקסיטי איז אָ (n).

ספעיס קאַמפּלעקסיטי

אָ (1): מיר נוצן קיין עקסטרע פּלאַץ.