Минимальные перестановки, чтобы сделать строки равными для решения Leetcode


Сложный уровень средний
Часто спрашивают в Амазонка
Жадный строка

Постановка задачи

Вам дается два струны s1 и s2 одинаковой длины, состоящие только из букв «x» и «y». вы можете поменять местами любые два символа, принадлежащие разным строкам,
ваша задача - сделать обе строки равными. вернуть минимальное количество перестановок, необходимых для того, чтобы обе строки стали равными, или -1, если невозможно сделать обе строки равными.

Пример

#1

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

#2

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

Подход (Жадный)

Если мы посмотрим на символы в обеих строках в некотором i-м индексе, мы обнаружим, что существует только 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].

Минимальные перестановки, чтобы сделать строки равными для решения Leetcode

 

(ii) если у нас есть 3-й тип пары с индексом i и 4-й тип пары с некоторым индексом j (или наоборот): {«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].

 

Минимальные перестановки, чтобы сделать строки равными для решения Leetcode

 

как мы видим, операция типа (i) требует всего 1 шага для установки двух индексов, поэтому мы постараемся выполнять операции типа (i) столько, сколько сможем. мы можем легко подсчитать все
типы пар. Допустим, мы получили количество пар {"x", "y"} = n1, количество пар {"y", "x"} = n2.
мы можем рассчитаться по 2 парам типа 3 за один обмен. поэтому общий своп, который нам нужен для урегулирования n1 пар, будет равен n1 / 2, если n1 нечетное, одна пара останется невыполненной.

Аналогично для n2. если n1 и n2 нечетные, мы получим по одной паре каждого невыполненного, поэтому мы можем использовать операцию типа (ii), которая требует 2 перестановок для их урегулирования.
в противном случае, если четность n1 и n2 не одинакова (т.е. n1 нечетно, а n2 четно), то мы получим одну пару, которая не рассчитана,
в таком случае уравнять струны будет невозможно.

Реализация

Программа C ++ для минимальной замены, чтобы сделать строки равными с решением Leetcode

#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 для минимальной замены, чтобы сделать строки равными с решением Leetcode

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

Анализ сложности для минимальных свопов, чтобы строки были равны решению Leetcode

Сложность времени

На) : Где n - длина строки. Поскольку мы повторяем обе строки только один раз, поэтому временная сложность будет O (n).

Космическая сложность

О (1): Мы не используем лишнего места.