I am not able to find a wrong test case so can anybody help me with that.
I made a frequency vector for all alphabets a(26,0).
Then made a prefix array for all alphabets b[26][n+1].
In the last I calculated the number of swapping (c) needed to make for each indice by the formula c = a[t] - (b[t][a[t] + i] - b[t][I]).
This is the code. include <bits/stdc++.h> define dbg(var) cout<<#var<<“=”<<var<<" "
using namespace std;
typedef long long ll;
typedef vector vi;
typedef pair<int, int> pi; define pb push_back define f first define s second
const ll inf = 1e18;
const ll mod = 1e9 + 7;
// string s;
// int a[200000], ps[200001][31] = {0};
void solve()
{
ll n;
string s;
cin >> s;
n = s.length();
vectora(26,0);
for (ll i = 0; i < n; i++)
{
a[s[i] - ‘a’]++;
}
ll b[26][n + 1];
for (ll i = 0; i < 26; i++)
{
for (ll j = 0; j <= n; j++)
{
b[i][j] = 0;
}
}
for (ll i = 0; i < 26; i++)
{
for (ll j = 1; j <= n; j++)
{
b[i][j] = b[i][j - 1];
if (s[j - 1] == (char)(i + ‘a’))
{
b[i][j]++;
}
}
}
ll c = inf;
ll ans = inf;
ll t;
for (ll i = 0; i < n; i++)
{
t = s[i] - ‘a’;
if (a[t] + i > n)
continue;
c = a[t] - (b[t][a[t] + i] - b[t][i]);
// dbg(c);
ans = min(ans, c);
}
cout << ans << “\n”;
}
int32_t main()
{
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout); // take input from the file and O/P on the console-- > more clarity!
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
When iterating over positions i, not only str_i but all characters must be checked if they can form a contiguous segment starting from i. Consider the test case:
1
baabbaaba
Here, it is optimal to form a contiguous segment of b starting from index 2 (0-based indexing).
(Also, it would make convenient reading if you format the codes included in the post).
#include <bits/stdc++.h>
#define dbg(var) cout<<#var<<"="<<var<<" "
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define f first
#define s second
const ll inf = 1e18;
const ll mod = 1e9 + 7;
// string s;
// int a[200000], ps[200001][31] = {0};
void solve()
{
ll n;
string s;
cin >> s;
n = s.length();
vector<ll>fr(26,0);
for (ll i = 0; i < n; i++)
{
fr[s[i] - 'a']++;
}
ll pr[26][n + 1];
for (ll i = 0; i < 26; i++)
{
for (ll j = 0; j <= n; j++)
{
pr[i][j] = 0;
}
}
for (ll i = 0; i < 26; i++)
{
for (ll j = 1; j <= n; j++)
{
pr[i][j] = pr[i][j - 1];
if (s[j - 1] == (char)(i + 'a'))
{
pr[i][j]++;
}
}
}
ll eswap = inf;
ll ans = inf;
ll alphabet;
for (ll i = 0; i < n; i++)
{
alphabet = s[i] - 'a';
if (fr[alphabet] + i > n)
continue;
eswap = fr[alphabet] - (pr[alphabet][fr[alphabet] + i] - pr[alphabet][i]);
ans = min(ans, eswap);
}
cout << ans << "\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Here I changed some of the variables name for proper understanding of the code.I also ran the test case provided by you and the output was 2 which is correct.
Thankyou for your reply.