Мінімальні обміни, щоб зробити струни рівними рішенням для штрих-коду


Рівень складності Medium
Часто запитують у Амазонка
Жадібний рядок

Постановка проблеми

Вам дають два струни 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].

Мінімальні обміни, щоб зробити струни рівними рішенням для штрих-коду

 

(ii) якщо у нас є 3-й тип пари за індексом i та 4-й тип пари за деяким індексом j (або навпаки): {“x”, ”y”}, {“y”, ”x”}. отже, зробити s1 [i] = s2 [i] та
s1 [j] = s2 [j] нам потрібно помінятися місцями двічі, спочатку нам потрібно поміняти місцями s1 [i] на s2 [i], тепер пари виглядатимуть так: {“y”, ”x”}, {“y, ”X”}. тепер нам потрібно поміняти місцями s1 [i] на s2 [j], і ми отримаємо
s1 [i] = s2 [i] та s1 [j] = s2 [j].

 

Мінімальні обміни, щоб зробити струни рівними рішенням для штрих-коду

 

як ми можемо бачити, операція типу (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

Складність часу

O (n): Де n - довжина рядка. Оскільки ми повторюємо обидва рядки лише один раз, отже, складність часу буде O (n).

Складність простору

O (1): Ми не використовуємо зайвий простір.