PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mamaleshrh
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Prefix sums or binary search
PROBLEM:
You’re given a string S. In one move, you can swap any two of its characters.
Find the minimum number of swaps needed to make all the occurrences of some character form a contiguous substring.
EXPLANATION:
Let’s fix a character, say 'a'.
What’s the minimum number of swaps we need to get all occurrences of 'a' to be next to each other?
Answer
Let the total number of occurrences of 'a' in S be k.
These k occurrences should then be brought into a window of size k.
Suppose we fix the left endpoint of this window to L, that is, we try to bring the occurrences of 'a' to indices L, L+1, L+2, \ldots, L+k-1.
To do this:
- Any
'a'that already appears in this window doesn’t need to be moved. - Any
'a'that is initially outside this window requires one swap to be moved into it.
So, all we need to do is find the number of occurrences of 'a' that are outside this window.
That’s quite easy, and can be done in several ways:
- One way is to use prefix sums.
- Let \text{pref}_i denote the number of occurrences of
'a'in the first i positions. - Then, the number of
'a'that appear outside the range [L, L+k-1] is just \text{pref}_{L-1} + (\text{pref}_N - \text{pref}_{L+k-1}).
- Let \text{pref}_i denote the number of occurrences of
- Alternately, you can use binary search: store a sorted list of positions of occurrences of
'a', and use binary search to find the number of these positions that are \lt L or \gt L+k-1.
This can also be done with two pointers instead of binary search.
Either way, it’s possible to check a single index L quickly, so check all possible L as starting positions and take the best among them.
For a single character, this check was performed in \mathcal{O}(N) or \mathcal{O}(N\log N) time.
All that needs to be done is to perform this check for every character from 'a' to 'z', and take the minimum among them all.
TIME COMPLEXITY:
\mathcal{O}(26 N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
//#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>//oset name name.order_of_key(#ele<k) *name.find_by_order(index) less_equal greater greater_equal
#define vi vector<int>
#define pii pair<int,int>
#define mii map<int,int>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define int long long
#define ld long double
#define pb push_back
#define all(v) v.begin(), v.end()
#define back(v) v.rbegin(), v.rend()
#define yes cout << "YES" <<"\n";
#define no cout << "NO" <<"\n";
#define deb(a) cerr<< #a << "=" << (a)<<"\n";
#define nl "\n"
#define FastIO \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
using namespace std;
#define mod 1000000007
const int oo = 1e18;
void solve()
{
string s;cin>>s;
vector<vi>occur(26);
for(int i=0;i<s.size();i++){
occur[s[i]-'a'].pb(i);
}
int out=oo;
for(int i=0;i<26;i++){
int l=0;int r =0;
int j=0;
for(int l=0;l<occur[i].size();l++){
while(r<occur[i].size()&&occur[i][r]-occur[i][l]+1<=occur[i].size()){
out=min(out,(int)(occur[i].size()-(r-l+1)));
r++;
}
}
}
cout<<out<<nl;
}
signed main()
{
FastIO;
// freopen("P5_5.in", "r", stdin);
// freopen("P5_5.out", "w", stdout);
int test=1;
cin >> test;
while (test--)
{
solve();
}
return 0;
}
Editorialist's code (Python)
import string
for _ in range(int(input())):
s = input()
n = len(s)
ans = n
for c in string.ascii_lowercase:
ct = s.count(c)
if ct == 0: continue
have = 0
for i in range(ct):
have += s[i] == c
ans = min(ans, ct - have)
for i in range(ct, n):
have += s[i] == c
have -= s[i-ct] == c
ans = min(ans, ct - have)
print(ans)