ਸਟ੍ਰਿੰਗਜ਼ ਦੇ ਬਰਾਬਰ ਲੀਟਕੋਡ ਘੋਲ ਬਣਾਉਣ ਲਈ ਘੱਟੋ ਘੱਟ ਸਵੈਪ  


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ
ਐਲਗੋਰਿਥਮ ਕੋਡਿੰਗ ਲਾਲਚੀ ਇੰਟਰਵਿਊ ਇੰਟਰਵਿ interview ਦੀ ਤਿਆਰੀ ਲੀਟਕੋਡ LeetCodeSolutions ਸਤਰ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ  

ਤੁਹਾਨੂੰ ਦੋ ਦਿੱਤੇ ਗਏ ਹਨ ਸਤਰ s1 ਅਤੇ s2 ਬਰਾਬਰ ਲੰਬਾਈ ਦੇ ਅੱਖਰ "x" ਅਤੇ "y" ਹੀ ਹੁੰਦੇ ਹਨ. ਤੁਸੀਂ ਕਿਸੇ ਵੀ ਦੋ ਅੱਖਰ ਨੂੰ ਵੱਖ ਵੱਖ ਸਤਰਾਂ ਨਾਲ ਜੋੜ ਸਕਦੇ ਹੋ,
ਤੁਹਾਡਾ ਕੰਮ ਦੋਵਾਂ ਸਤਰਾਂ ਨੂੰ ਬਰਾਬਰ ਕਰਨਾ ਹੈ. ਦੋਵੇਂ ਸਤਰਾਂ ਨੂੰ ਬਰਾਬਰ ਜਾਂ -1 ਬਣਾਉਣ ਲਈ ਘੱਟੋ ਘੱਟ ਸਵੈਪ ਦੀ ਲੋੜੀਂਦੀ ਗਿਣਤੀ ਵਾਪਸ ਕਰੋ ਜੇ -XNUMX ਜੇ ਦੋਵੇਂ ਸਤਰਾਂ ਨੂੰ ਬਰਾਬਰ ਕਰਨਾ ਅਸੰਭਵ ਹੈ.

ਉਦਾਹਰਨ

#1

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

#2

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

ਪਹੁੰਚ (ਲਾਲਚੀ)  

ਜੇ ਅਸੀਂ ਕੁਝ ith ਸੂਚਕਾਂਕ ਦੀਆਂ ਦੋਵੇਂ ਸਤਰਾਂ ਦੇ ਪਾਤਰਾਂ ਨੂੰ ਵੇਖੀਏ, ਤਾਂ ਅਸੀਂ ਇਹ ਵੇਖਾਂਗੇ ਕਿ ਇੱਥੇ ਸਿਰਫ 4 ਸੰਭਾਵਿਤ ਜੋੜੇ ਹਨ {s1 [i], s2 [i]}: x “x”, ”x”}, {“y , "Y"}, {"x", "y"}, {"y", "x"}.
ਪਹਿਲੇ ਦੋ ਕਿਸਮਾਂ ਦੇ ਜੋੜਾਂ ਲਈ S1 [i] s2 ਦੇ ਬਰਾਬਰ ਹੈ [i] (ਇਹ ਉਹ ਹੈ ਜੋ ਅਸੀਂ ਚਾਹੁੰਦੇ ਹਾਂ), ਅਜਿਹੇ ਸਵੈਪਾਂ ਦੀ ਜ਼ਰੂਰਤ ਅਜਿਹੇ ਮਾਮਲਿਆਂ ਲਈ ਜ਼ੀਰੋ ਹੋਵੇਗੀ.

ਬਾਕੀ ਜੋੜੀ ਜੋ ਸਾਡੇ ਕੋਲ s1 ਹਨ [i] ਐਸ 2 ਦੇ ਬਰਾਬਰ ਨਹੀਂ ਹਨ [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].

ਇਹ ਵੀ ਵੇਖੋ
ਕ੍ਰਮਬੱਧ ਮੈਟ੍ਰਿਕਸ ਵਿਚ ਕੇ-ਵੇਂ ਸਭ ਤੋਂ ਛੋਟਾ ਤੱਤ

ਸਟ੍ਰਿੰਗਜ਼ ਦੇ ਬਰਾਬਰ ਲੀਟਕੋਡ ਘੋਲ ਬਣਾਉਣ ਲਈ ਘੱਟੋ ਘੱਟ ਸਵੈਪ

 

(ii) ਜੇ ਸਾਡੇ ਕੋਲ ਇੰਡੈਕਸ i ਤੇ ਤੀਜੀ ਕਿਸਮ ਦੀ ਜੋੜੀ ਹੈ ਅਤੇ ਕੁਝ ਇੰਡੈਕਸ ਜੇ (ਜਾਂ ਇਸਦੇ ਉਲਟ) ਤੇ ਚੌਥੀ ਕਿਸਮ ਦੀ ਜੋੜੀ: {"x", "y"}, {"y", "x"}. ਇਸ ਲਈ, s3 ਬਣਾਉਣ ਲਈ [i] = s4 [i] ਅਤੇ
s1 [j] = s2 [j] ਸਾਨੂੰ ਦੋ ਵਾਰ ਸਵੈਪ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ, ਪਹਿਲਾਂ ਸਾਨੂੰ s1 [i] ਨੂੰ s2 ਨਾਲ ਬਦਲਣਾ ਚਾਹੀਦਾ ਹੈ [i], ਹੁਣ ਜੋੜੀਆਂ ਦਿਖਾਈ ਦੇਣਗੀਆਂ: {“y”, “x”}, {“y, ”X”}. ਹੁਣ ਸਾਨੂੰ s1 [i] ਨੂੰ s2 [j] ਨਾਲ ਬਦਲਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਅਤੇ ਅਸੀਂ ਪ੍ਰਾਪਤ ਕਰਾਂਗੇ
s1 [i] = s2 [i] ਅਤੇ ਐਸ 1 [ਜੇ] = ਐਸ 2 [ਜੇ].

 

ਸਟ੍ਰਿੰਗਜ਼ ਦੇ ਬਰਾਬਰ ਲੀਟਕੋਡ ਘੋਲ ਬਣਾਉਣ ਲਈ ਘੱਟੋ ਘੱਟ ਸਵੈਪ

 

ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਵੇਖ ਸਕਦੇ ਹਾਂ (i) ਟਾਈਪ ਓਪਰੇਸ਼ਨ ਦੋ ਸੂਚਕਾਂਕ ਦਾ ਨਿਪਟਾਰਾ ਕਰਨ ਲਈ ਸਿਰਫ 1 ਚਾਲ ਲੈਂਦਾ ਹੈ, ਇਸ ਲਈ ਅਸੀਂ (i) ਕਿਸਮ ਦੇ ਓਪਰੇਸ਼ਨ ਜਿੰਨੇ ਅਸੀਂ ਕਰ ਸਕਦੇ ਹਾਂ ਬਣਾਉਣ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰਾਂਗੇ. ਅਸੀਂ ਆਸਾਨੀ ਨਾਲ ਸਭ ਦੀ ਗਿਣਤੀ ਪ੍ਰਾਪਤ ਕਰ ਸਕਦੇ ਹਾਂ
ਜੋੜਿਆਂ ਦੀਆਂ ਕਿਸਮਾਂ. ਮੰਨ ਲਓ ਕਿ ਸਾਡੇ ਕੋਲ {"x", "y"} ਜੋੜੇ = n1, {"y", "x"} ਜੋੜੇ = n2 ਦੀ ਗਿਣਤੀ ਮਿਲਦੀ ਹੈ.
ਅਸੀਂ ਇਕ ਜੋੜੀ ਵਿਚ ਟਾਈਪ 2 ਦੇ 3 ਜੋੜੇ ਸੈਟਲ ਕਰ ਸਕਦੇ ਹਾਂ. ਇਸ ਲਈ ਕੁੱਲ ਸਵੈਪ ਜੋ ਸਾਨੂੰ N1 ਜੋੜਿਆਂ ਨੂੰ ਸੈਟਲ ਕਰਨ ਦੀ ਜਰੂਰਤ ਹੈ ਉਹ N1 / 2 ਹੋਵੇਗਾ, ਜੇ n1 ਅਜੀਬ ਹੈ ਤਾਂ ਇੱਕ ਜੋੜਾ ਨਿਰਵਿਘਨ ਰਹਿ ਜਾਵੇਗਾ.

ਇਸੇ ਤਰ੍ਹਾਂ ਐਨ 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) ਹੋਵੇਗੀ.

ਇਹ ਵੀ ਵੇਖੋ
ਸਟਾਕ III ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਨੂੰ ਖਰੀਦਣ ਅਤੇ ਵੇਚਣ ਦਾ ਸਭ ਤੋਂ ਵਧੀਆ ਸਮਾਂ

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1): ਅਸੀਂ ਕੋਈ ਵਧੇਰੇ ਥਾਂ ਨਹੀਂ ਵਰਤ ਰਹੇ ਹਾਂ.

1