fork download
copy 
  1. /*
  2. QUESTION 7: Minimum Inversion Interleaving of Two Strings
  3.  
  4. Problem Statement:
  5. You are given two strings s and t.
  6.  
  7. Create one final string by interleaving their characters.
  8.  
  9. Rules:
  10. - s must remain a subsequence of the final string.
  11. - t must remain a subsequence of the final string.
  12. - Internal order of both strings must be preserved.
  13.  
  14. An inversion is a pair i < j such that:
  15. finalString[i] > finalString[j]
  16.  
  17. Return the minimum possible inversion count.
  18.  
  19. Hard Constraints:
  20. 1 <= |s|, |t| <= 3000
  21. Strings contain lowercase English letters.
  22.  
  23. Example:
  24. s = "ca"
  25. t = "bb"
  26.  
  27. Expected Output:
  28. 3
  29.  
  30. Explanation:
  31. One optimal merge is:
  32. "bbca"
  33.  
  34. Inversions:
  35. b > a
  36. b > a
  37. c > a
  38.  
  39. Total = 3
  40.  
  41. Brute Force:
  42. Generate every possible interleaving of s and t.
  43. Count inversions in each one.
  44. Return the minimum.
  45.  
  46. Time Complexity:
  47. Exponential
  48.  
  49. Optimized Approach:
  50. Use DP.
  51.  
  52. dp[i][j] =
  53. minimum inversions after using first i characters of s and first j characters of t.
  54.  
  55. At each state:
  56. - place next character from s
  57. - or place next character from t
  58.  
  59. When placing a character, count how many already placed characters are greater than it.
  60.  
  61. Use prefix frequency arrays for fast counting.
  62.  
  63. Time Complexity:
  64. O(|s| * |t| * 26)
  65.  
  66. Space Complexity:
  67. O(|s| * |t|)
  68. */
  69.  
  70. #include <bits/stdc++.h>
  71. using namespace std;
  72.  
  73. class Solution {
  74. public:
  75.     long long minimumInversionsAfterMerge(string s, string t) {
  76.         int n = s.size();
  77.         int m = t.size();
  78.  
  79.         vector<array<int, 26>> prefS(n + 1), prefT(m + 1);
  80.  
  81.         for (int c = 0; c < 26; c++) {
  82.             prefS[0][c] = 0;
  83.             prefT[0][c] = 0;
  84.         }
  85.  
  86.         for (int i = 0; i < n; i++) {
  87.             prefS[i + 1] = prefS[i];
  88.             prefS[i + 1][s[i] - 'a']++;
  89.         }
  90.  
  91.         for (int i = 0; i < m; i++) {
  92.             prefT[i + 1] = prefT[i];
  93.             prefT[i + 1][t[i] - 'a']++;
  94.         }
  95.  
  96.         auto greaterCount = [&](array<int, 26>& freq, int ch) {
  97.             int cnt = 0;
  98.  
  99.             for (int c = ch + 1; c < 26; c++) {
  100.                 cnt += freq[c];
  101.             }
  102.  
  103.             return cnt;
  104.         };
  105.  
  106.         const long long INF = 4e18;
  107.  
  108.         vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, INF));
  109.         dp[0][0] = 0;
  110.  
  111.         for (int i = 0; i <= n; i++) {
  112.             for (int j = 0; j <= m; j++) {
  113.                 if (dp[i][j] == INF) continue;
  114.  
  115.                 if (i < n) {
  116.                     int ch = s[i] - 'a';
  117.  
  118.                     int add =
  119.                         greaterCount(prefS[i], ch) +
  120.                         greaterCount(prefT[j], ch);
  121.  
  122.                     dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + add);
  123.                 }
  124.  
  125.                 if (j < m) {
  126.                     int ch = t[j] - 'a';
  127.  
  128.                     int add =
  129.                         greaterCount(prefS[i], ch) +
  130.                         greaterCount(prefT[j], ch);
  131.  
  132.                     dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + add);
  133.                 }
  134.             }
  135.         }
  136.  
  137.         return dp[n][m];
  138.     }
  139. };
  140.  
  141. int main() {
  142.     Solution sol;
  143.  
  144.     string s = "ca";
  145.     string t = "bb";
  146.  
  147.     cout << sol.minimumInversionsAfterMerge(s, t) << endl;
  148.  
  149.     return 0;
  150. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/7dvFvS
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!