Vowel_Swap - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Author: Ansh Varshney
Tester: Shivansh Gupta
Editorialist: Ansh Varshney

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Precomputation , Median , Array

PROBLEM:

As Chef was tired and busy sleeping so he decided to give you a string of length N consisting of consonants and vowels. You need to form a group of all vowels together in the minimum number of adjacent swaps.

QUICK EXPLANATION:

First of all place all the vowels in an array then find meddle index of the array in which vowel is stored and bring all vowel close to it .

EXPLANATION:

Form a Vowel Array of all the vowel present in the string ,take a variable count (for counting the moves) and then find the middle index (Median) of the array . Let say the median index is Vx then from 0<=i<=x-1 bring all the vowel close to the median index and at the same time count the moves ,from x+1<=i<=vowel.size() bring all the vowel close to median index and at the same time count the moves.

SOLUTIONS:

Setter's Solution 
  #include <bits/stdc++.h>

  using namespace std;

  bool is_vowel(char ch)

  {

      if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')

        return true;

    return false;

  }

int main()

{

    int t;

    cin >> t;

    while (t--)

    {

        int n;

        cin >> n;

        string s;

        cin >> s;

        vector<int> temp;

        for (int i = 0; i < n; i++)

        {

            if (is_vowel(s[i]))

                temp.push_back(i);

        }

        int mid = temp.size() / 2;

        int x = mid - 1, y = mid + 1;

        int count = 0;

        int middle = mid;

        while (x >= 0)

        {

            count = count + temp[middle] - temp[x] - 1;

            temp[x] = temp[middle] - 1;

            middle--;

            x--;

        }

        middle = mid;

        while (y < temp.size())

        {

            count = count + temp[y] - temp[middle] - 1;

            temp[y] = temp[middle] + 1;

            y++;

            middle++;

        }

        cout << count << endl;

    }

    return 0;

}
Tester's Solution 
    #include <bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    #define endl "\n"

    bool is_vowel(char ch)

     {

      if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')

        return true;

    return false;

   }

   void solve()

  {

      ll n, vs, ans, k;

      string s;

      cin >> n >> s;

      vector<ll> vowel, pref, suff;

      for (int i = 0; i < n; i++)

        if (is_vowel(s[i]))

        {

            vowel.push_back(i);

            pref.push_back(i);

            suff.push_back(i);

        }

      vs = vowel.size();

      if(vs==0)

    {

        cout<<0<<endl;

        return;

    }

    for (int i = 1; i < vs; i++)

        pref[i] += pref[i - 1];

    for (int i = vs - 2; i >= 0; i--)

        suff[i] += suff[i + 1];

    ans = suff[0] - ((vs - 1) * vs / 2 + vs * vowel[0]);

    for (int i = 1; i < vs; i++)

    {

        k = (suff[i] - ((vs - i - 1) * (vs - i) / 2 + (vs - i) * vowel[i]));

        k -= (pref[i - 1] - (i * vowel[i] - i * (i + 1) / 2));

        ans = min(ans, k);        

    }

    cout << ans << endl;

}

int main()

{

    int t;

    cin >> t;

    while (t--)

        solve();

    return 0;

}
Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;

bool is_vowel(char ch)
{
    if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
        return true;
    return false;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> temp;
        for (int i = 0; i < n; i++)
        {  
            if (is_vowel(s[i]))
                temp.push_back(i);
        }
        int mid = temp.size() / 2;
        int x = mid - 1, y = mid + 1;
        int count = 0;
        int middle = mid;
        while (x >= 0)
        {
            count = count + temp[middle] - temp[x] - 1;
            temp[x] = temp[middle] - 1;
            middle--;
            x--;
        }
        middle = mid;
        while (y < temp.size())
        {
            count = count + temp[y] - temp[middle] - 1;
            temp[y] = temp[middle] + 1;
            y++;
            middle++;
        }
        cout << count << endl;
    }
    return 0;
}
1 Like