fork download
copy 
  1. /*
  2.     Problem: Sum of Palindrome Rearrangement Costs of All Substrings
  3.     Company Tag: Intuit OA
  4.  
  5.     Problem Statement:
  6.         We are given a string s.
  7.  
  8.         For any substring of s, its cost is the minimum number of character
  9.         replacements needed so that the substring can be rearranged to form
  10.         a palindrome.
  11.  
  12.         A string can be rearranged into a palindrome if at most one character
  13.         has odd frequency.
  14.  
  15.         For a substring:
  16.             oddCount = number of characters having odd frequency
  17.  
  18.         If oddCount is 0 or 1:
  19.             cost = 0
  20.  
  21.         If oddCount is greater than 1:
  22.             One replacement can fix two odd-frequency characters.
  23.  
  24.         So:
  25.             cost = oddCount / 2
  26.  
  27.         Return the sum of costs over all substrings.
  28.  
  29.     Constraints:
  30.         1 <= s.length <= 200000
  31.         s consists of lowercase English letters.
  32.  
  33.     Brute Force:
  34.         Generate every substring.
  35.         For each substring, count character frequencies and calculate cost.
  36.  
  37.     Why Brute Force Fails:
  38.         There are O(n^2) substrings.
  39.         Since n can be 200000, O(n^2) is too slow.
  40.  
  41.     Optimized Idea:
  42.         For every substring, I need to know how many characters have odd frequency.
  43.  
  44.         I use prefix parity mask.
  45.  
  46.         For every prefix:
  47.             bit c = 1 means character c has odd frequency till now.
  48.  
  49.         For substring l to r:
  50.             odd frequency mask = prefix[r + 1] XOR prefix[l]
  51.  
  52.         So I need:
  53.             sum of floor(popcount(prefix[i] XOR prefix[j]) / 2)
  54.             over all pairs of prefix masks.
  55.  
  56.         Formula:
  57.             floor(x / 2) = (x - (x % 2)) / 2
  58.  
  59.         So I calculate:
  60.             1. Total Hamming distance over all prefix mask pairs.
  61.             2. Number of pairs where Hamming distance is odd.
  62.  
  63.         Answer:
  64.             (totalHammingDistance - oddHammingPairs) / 2
  65.  
  66.     Dry Run:
  67.         s = "abc"
  68.  
  69.         Substrings:
  70.             "a"   -> oddCount = 1 -> cost = 0
  71.             "b"   -> oddCount = 1 -> cost = 0
  72.             "c"   -> oddCount = 1 -> cost = 0
  73.             "ab"  -> oddCount = 2 -> cost = 1
  74.             "bc"  -> oddCount = 2 -> cost = 1
  75.             "abc" -> oddCount = 3 -> cost = 1
  76.  
  77.         Total cost = 3
  78.  
  79.     Time Complexity:
  80.         O(26 * n)
  81.  
  82.     Space Complexity:
  83.         O(n)
  84. */
  85.  
  86. #include <bits/stdc++.h>
  87. using namespace std;
  88.  
  89. using ll = long long;
  90.  
  91. long long sumPalindromeRearrangementCosts(string s) {
  92.     int n = s.size();
  93.  
  94.     vector<int> prefixMasks;
  95.     prefixMasks.reserve(n + 1);
  96.  
  97.     int mask = 0;
  98.  
  99.     // Empty prefix mask.
  100.     prefixMasks.push_back(mask);
  101.  
  102.     for (char ch : s) {
  103.         int bit = ch - 'a';
  104.  
  105.         // Toggle the bit because frequency parity changes.
  106.         // If it was even, it becomes odd.
  107.         // If it was odd, it becomes even.
  108.         mask ^= (1 << bit);
  109.  
  110.         prefixMasks.push_back(mask);
  111.     }
  112.  
  113.     long long totalHammingDistance = 0;
  114.  
  115.     // For each character bit, count how many prefix masks have:
  116.     //      bit = 0
  117.     //      bit = 1
  118.     //
  119.     // Every pair with different bit values contributes 1 to Hamming distance.
  120.     for (int bit = 0; bit < 26; bit++) {
  121.         long long ones = 0;
  122.         long long zeros = 0;
  123.  
  124.         for (int m : prefixMasks) {
  125.             if (m & (1 << bit)) {
  126.                 ones++;
  127.             } else {
  128.                 zeros++;
  129.             }
  130.         }
  131.  
  132.         totalHammingDistance += ones * zeros;
  133.     }
  134.  
  135.     long long evenParityMasks = 0;
  136.     long long oddParityMasks = 0;
  137.  
  138.     // If two masks have different popcount parity,
  139.     // then their XOR has odd Hamming distance.
  140.     for (int m : prefixMasks) {
  141.         if (__builtin_popcount((unsigned int)m) % 2 == 0) {
  142.             evenParityMasks++;
  143.         } else {
  144.             oddParityMasks++;
  145.         }
  146.     }
  147.  
  148.     long long oddHammingPairs = evenParityMasks * oddParityMasks;
  149.  
  150.     // Applying:
  151.     //      floor(x / 2) = (x - (x % 2)) / 2
  152.     long long answer = (totalHammingDistance - oddHammingPairs) / 2;
  153.  
  154.     return answer;
  155. }
  156.  
  157. int main() {
  158.     string s = "abc";
  159.  
  160.     cout << sumPalindromeRearrangementCosts(s) << endl;
  161.  
  162.     return 0;
  163. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/QHp7zq
language:
C++14 (gcc 8.3)
created:
3 days 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!