int m = primary.size();
int n = secondary.size();
// Step 1: count fixed within-string inversions
int fixedInversions = 0;
// inversions within primary
for (int i = 0; i < m; i++)
for (int j = i + 1; j < m; j++)
if (primary[i] > primary[j]) fixedInversions++;
// inversions within secondary
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (secondary[i] > secondary[j]) fixedInversions++;
// Step 2: precompute prefix tables
// greaterInPrimary[i][c] = how many chars in primary[0..i-1] are > 'a'+c
vector<vector<int>> greaterInPrimary(m + 1, vector<int>(26, 0));
for (int i = 1; i <= m; i++) {
for (int c = 0; c < 26; c++)
greaterInPrimary[i][c] = greaterInPrimary[i-1][c];
// primary[i-1] is greater than all chars with ASCII < primary[i-1]
for (int c = 0; c < (primary[i-1] - 'a'); c++)
greaterInPrimary[i][c]++;
}
// greaterInSecondary[j][c] = how many chars in secondary[0..j-1] are > 'a'+c
vector<vector<int>> greaterInSecondary(n + 1, vector<int>(26, 0));
for (int j = 1; j <= n; j++) {
for (int c = 0; c < 26; c++)
greaterInSecondary[j][c] = greaterInSecondary[j-1][c];
for (int c = 0; c < (secondary[j-1] - 'a'); c++)
greaterInSecondary[j][c]++;
}
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
// base cases: no cross conflicts if only one string placed
for (int i = 0; i <= m; i++) dp[i][0] = 0;
for (int j = 0; j <= n; j++) dp[0][j] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int conflictP = greaterInSecondary[j][primary[i-1] - 'a'];
if (dp[i-1][j] != INT_MAX)
dp[i][j] = min(dp[i][j], dp[i-1][j] + conflictP);
// Option 2: place secondary[j-1] next
// cross conflicts added = primary chars already placed
// that are greater than secondary[j-1]
int conflictS = greaterInPrimary[i][secondary[j-1] - 'a'];
if (dp[i][j-1] != INT_MAX)
dp[i][j] = min(dp[i][j], dp[i][j-1] + conflictS);
}
}
return fixedInversions + dp[m][n];