/*
QUESTION 7: Minimum Inversion Interleaving of Two Strings

Problem Statement:
You are given two strings s and t.

Create one final string by interleaving their characters.

Rules:
- s must remain a subsequence of the final string.
- t must remain a subsequence of the final string.
- Internal order of both strings must be preserved.

An inversion is a pair i < j such that:
finalString[i] > finalString[j]

Return the minimum possible inversion count.

Hard Constraints:
1 <= |s|, |t| <= 3000
Strings contain lowercase English letters.

Example:
s = "ca"
t = "bb"

Expected Output:
3

Explanation:
One optimal merge is:
"bbca"

Inversions:
b > a
b > a
c > a

Total = 3

Brute Force:
Generate every possible interleaving of s and t.
Count inversions in each one.
Return the minimum.

Time Complexity:
Exponential

Optimized Approach:
Use DP.

dp[i][j] =
minimum inversions after using first i characters of s and first j characters of t.

At each state:
- place next character from s
- or place next character from t

When placing a character, count how many already placed characters are greater than it.

Use prefix frequency arrays for fast counting.

Time Complexity:
O(|s| * |t| * 26)

Space Complexity:
O(|s| * |t|)
*/

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long minimumInversionsAfterMerge(string s, string t) {
        int n = s.size();
        int m = t.size();

        vector<array<int, 26>> prefS(n + 1), prefT(m + 1);

        for (int c = 0; c < 26; c++) {
            prefS[0][c] = 0;
            prefT[0][c] = 0;
        }

        for (int i = 0; i < n; i++) {
            prefS[i + 1] = prefS[i];
            prefS[i + 1][s[i] - 'a']++;
        }

        for (int i = 0; i < m; i++) {
            prefT[i + 1] = prefT[i];
            prefT[i + 1][t[i] - 'a']++;
        }

        auto greaterCount = [&](array<int, 26>& freq, int ch) {
            int cnt = 0;

            for (int c = ch + 1; c < 26; c++) {
                cnt += freq[c];
            }

            return cnt;
        };

        const long long INF = 4e18;

        vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, INF));
        dp[0][0] = 0;

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (dp[i][j] == INF) continue;

                if (i < n) {
                    int ch = s[i] - 'a';

                    int add =
                        greaterCount(prefS[i], ch) +
                        greaterCount(prefT[j], ch);

                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + add);
                }

                if (j < m) {
                    int ch = t[j] - 'a';

                    int add =
                        greaterCount(prefS[i], ch) +
                        greaterCount(prefT[j], ch);

                    dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + add);
                }
            }
        }

        return dp[n][m];
    }
};

int main() {
    Solution sol;

    string s = "ca";
    string t = "bb";

    cout << sol.minimumInversionsAfterMerge(s, t) << endl;

    return 0;
}